AcWing 135. 最大子序和
原题链接
简单
- 固定左端点开始往右遍历,如果长度超过要求,就弹出左端点
- 如果当前点的前缀和小于队尾点的前缀和,就弹出队尾点,这样才能遍历到所有情况
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 300004;
int a[N];
deque<long long> q;
int m,n;
int ans = -999;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
q.push_back(0);
for(int i=1;i<=n;i++)
{
if(q.size() && i-m>q.front() )
q.pop_front();
if(q.size())
ans = max(ans, a[i]-a[q.front()]);
while(q.size() && a[i]<=a[q.back()])
q.pop_back();
q.push_back(i);
}
cout<<ans<<endl;
return 0;
}