AcWing 135. 最大子序和
原题链接
简单
作者:
cwr
,
2023-02-10 02:58:30
,
所有人可见
,
阅读 113
C++ 代码
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N=3e5+10,INF=0x3f3f3f3f;
int n,m;
int a[N];
int s[N];
int q[N];
int res;
int main() {
// FAST;
cin>>n>>m;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
res=-INF;
int tt=0,hh=0;//此处tt!=-1,因为需要存储s[0]的下标0
for(int i=1;i<=n;i++) {//集合划分:以为个数字结尾的区间的最大值中的最大值
//使用单调队列维护长度在1-m之间的是s[j]的最小值
if(i-m>q[hh]) hh++;//此处为i-m而不是i-m+1,因为存储的是前缀和的下标
res=max(res,s[i]-s[q[hh]]);
while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
q[++tt]=i;
}
cout<<res;
return 0;
}