最大子序和

链接：https://ac.nowcoder.com/acm/contest/33433/D 来源：牛客网

题目描述：第一行两个数n,m（n,m \leq 300000）（n,m≤300000） 第二行有n个数，要求在n个数找到最大子序和 输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。 例如 1,-3,5,1,-2,3 当m=4时，S=5+1-2+3=7 当m=2或m=3时，S=5+1=6

输入描述：第一行两个数n,m（n,m \leq 300000）（n,m≤300000） 第二行有n个数，要求在n个数找到最大子序和

输出描述：一个数，数出他们的最大子序和

#include<limits.h>
using namespace std;
//原理：由题意易得，我们要得到序列中长度不超过m的最大子段和。
//一初见：暴力，两重循环比较
//二优化：观察发现，我们只要减去终点之前m个前缀和的最小的那个所
//       得到的就是该终点处最大的不超过m长度的字段和，不断比较就能得到答案。
//三：故利用单调队列，令队头为范围内最小的前缀和，若超出范围则将队头弹出
//四：每次更新队列，将当前前缀和排入
typedef long long LL;
int q[300005];
LL sum[300005];
int main(){
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)//读入并计算前缀和
    {
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    int tt=0,hh=0;//hh为单调队列队头，tt为单调队列队尾
    LL res=INT_MIN;//res取int最小值
    for(i=1;i<=n;i++)
    {
        if(i-q[hh]>m) hh++;//若队头已经不在范围内，则队头后移（为什么后移一位就在范围内了呢？）
        //因为每次排入的时候tt都会改变，从而保证了队头后的元素都比队头大
        res=max(res,sum[i]-sum[q[hh]]);//比较
        while(hh<=tt&&sum[i]<=sum[q[tt]]) tt--;//若hh~tt内还有元素，则试图将sum[i]排入
        q[++tt]=i;
    }
    cout<<res<<endl;
    return 0;
}