C++(g++ 7.5.0) 解法, 执行用时: 34ms, 内存消耗: 3304K, 提交时间: 2022-11-16 19:10:36

#include<iostream>
using namespace std;
const int N=50000010;
int q[N],a[N],s[N],tt,hh;
void push(int x)
{
    q[++tt]=x;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
    }
    int ans=-1e8;
    for(int i=1;i<=n;i++){
        while(hh<=tt&&q[hh]<i-k) hh++;
        if(hh>tt) ans=max(ans,s[i]);
        else ans=max(ans,s[i]-s[q[hh]]);
        while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
        push(i);    
    }
    cout<<ans;
}

C++14(g++5.4) 解法, 执行用时: 64ms, 内存消耗: 1932K, 提交时间: 2020-10-16 20:05:58

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,M;
    cin>>N>>M;
    vector<int> A(N+1);
    for(int i=1;i<=N;i++)
    cin>>A[i];
    partial_sum(A.begin(),A.end(),A.begin());
    deque<int> Q;
    int ans=-0x3f3f3f3f;
    for(int i=0;i<=N;i++)
    {
        if(i>0)
        ans=max(ans,A[i]-Q.front());
        while(Q.size()&&Q.back()>A[i])
        Q.pop_back();
        Q.push_back(A[i]);
        if(i>=M&&A[i-M]==Q.front())
        Q.pop_front();
    }
    cout<<ans<<endl;
}

C++ 解法, 执行用时: 30ms, 内存消耗: 2696K, 提交时间: 2022-06-16 21:57:56

#include<bits/stdc++.h>
using namespace std;
int s[2000005];
int q[1000005];
int num[1000005];
int ans=-0x3f3f3f3f,i,n,m,h=1,t=1,x;
int main(){
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&x);
        s[i]=s[i-1]+x;
    }
    q[t]=num[t]=0;
    for(i=1; i<=n; i++)
    {
        while(num[h]<i-m&&h<=t)h++;
        ans=max(ans,s[i]-q[h]);
        while(q[t]>=s[i]&&h<=t)t--;
        q[++t]=s[i];
        num[t]=i;
    }
    printf("%d\n",ans);
    return 0;
}

Python3(3.5.2) 解法, 执行用时: 289ms, 内存消耗: 24720K, 提交时间: 2020-08-25 22:32:22

import collections

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))

s = [0]
for i in range(1, len(a)):
    s.append(s[-1] + a[i])
q = collections.deque()
q.append(0)
ans = float('-inf')
for i in range(1, n+1):
    while q and i - q[0] > m:
        q.popleft()
    ans = max(ans, s[i]-s[q[0]])
    while q and s[q[-1]] >= s[i]:
        q.pop()
    q.append(i)
print(ans)