【tyvj1305】最大子序和（单调队列）

problem

• 给你一个长为n的序列
• 求一个长不超过m的连续子段，使子段和最大

solution

• 如果n<=10^3，我们很容易写出枚举（s是前缀和，区间[l,r]的和就是s[r]-s[l-1]。枚举l,r即可。

for(int i = 1; i <= m; i++)//枚举长度
    for(int j = i; j <= n; j++)//枚举r
        ans = max(ans, s[j]-s[j-i]);//可以算出l

• 但是这里是10^5，，所以考虑进一步优化。
• 如果右端点是i，那么就转为求一个左端点j属于[i-m,i-1]并且s[j]最小。并且j越靠近m一定是越优的（在后面更不容易超过m。
• 所以选择集合一定是，“下标位置递增，对应前缀和s也递增”的序列，我们可以用队列保存这个序列。

codes

#include<iostream>
#include<algorithm>
#define maxn 300010
using namespace std;
int a[maxn], q[maxn];
long long s[maxn], ans;
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];  s[i]=s[i-1]+a[i];
    }
    int l = 1, r = 1;
    q[l] = 0; //save j
    for(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;
    }
    cout<<ans<<'\n';
    return 0;
}