C++(g++ 7.5.0) 解法, 执行用时: 41ms, 内存消耗: 2704K, 提交时间: 2023-07-26 14:55:59

#include<bits/stdc++.h>
using namespace std;
long long q[1000001],s[1000001];
int main(){
	long long x,n,l=1,r=1,m,ans=0;scanf("%lld%lld",&n,&m);q[1]=0;
	for(register int i=1;i<=n;++i)scanf("%lld",&x),s[i]=s[i-1]+x;
	for(register int i=1;i<=n;++i){
		while(l<=r&&q[l]<i-m)++l;
		ans=max(ans,s[i]-s[q[l]]);
		while(l<=r&&s[q[r]]>=s[i])--r;
		q[++r]=i;
	}
	printf("%lld",ans);
}

C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 2664K, 提交时间: 2020-01-23 15:11:16

#include<iostream>
#include<cstdio>
using namespace std;
long long sum[300010],ans;
int a,n,m,s[300010],l=1,r=1;
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a;
		sum[i]=sum[i-1]+a;
		while(l<=r&&s[l]<i-m) l++;
		ans=max(ans,sum[i]-sum[s[l]]);
		while(sum[s[r]]>=sum[i]&&r>=l) r--;
		s[++r]=i;
	}
	cout<<ans;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 80ms, 内存消耗: 2732K, 提交时间: 2022-09-20 21:53:30

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],s[N];
int main()
{
	int n,m,mx=0,l=1,r=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
		while(l<=r&&s[l]<i-m)l++;
		mx=max(mx,a[i]-a[s[l]]);
		while(a[s[r]]>=a[i]&&r>=l)r--;
		s[++r]=i;
	}
	cout<<mx<<'\n';
	return 0;
}

Python3 解法, 执行用时: 532ms, 内存消耗: 33364K, 提交时间: 2023-07-20 21:21:34

n,m=map(int,input().split())
arr=list(map(int,input().split()))
res=[]
ans=0
pre=[0]
for it in arr: pre.append(it+pre[-1])
for i in range(n+1):
    while res and res[0]+m<i: res.pop(0)
    if res: ans=max(ans,pre[i]-pre[res[0]])
    while res and pre[res[-1]]>pre[i]: res.pop()
    res.append(i)
print(ans)