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)