数数
解题思路
这题和假期(单调队列)差不多
AC代码
#include<iostream>
using namespace std;
long long a,n,k,s,head,tail,p[100005],sum[100005];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a;
sum[i]=sum[i-1]+a;//前缀和
}
s=-2147483647;//初值
head=tail=1;
for(int i=1;i<=n;i++)
{
while(sum[p[tail]]>=sum[i]&&head<=tail)tail--;//弹出
p[++tail]=i;//插入
while(p[head]<i-k&&head<=tail)head++;
s=max(s,sum[i]-sum[p[head]]);//求最大值
}
cout<<s;
}