[C++知识库]最大子序和

输入一个长度为 nn 的整数序列，从中找出一段长度不超过 mm 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 11。

输入格式

第一行输入两个整数 n,mn,m。

第二行输入 nn 个数，代表长度为 nn 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

1≤n,m≤3000001≤n,m≤300000

输入样例：

6 4
1 -3 5 1 -2 3

输出样例:

7

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int s[N],q[N],a[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    int mx=-N;
    int h=0,t=-1;
    q[++t]=0;
    for(int i=1;i<=n;i++)
    {
        if(h<=t&&q[h]<i-m)h++;
        mx=max(mx,s[i]-s[q[h]]);
        while(h<=t&&s[q[t]]>=s[i])
        t--;
        q[++t]=i;
    }
    cout<<mx<<endl;
    return 0;
}

涉及知识:单调队列，前缀和