《算法竞赛进阶指南》 最大子序和

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

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

输入格式

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

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

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

输出格式

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

数据范围

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

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

解题思路：

1:假设s[i]为a[i]的前缀和数组若要求出：一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
2:即求出s[i] - s[i - m + 1](m = 1, ..., m)的最大值
3:因为s[i]已固定, 即求出s[i - m + 1]最小值即可；
4:这里需要一个队列维护一个长度不大于m的数组，
当队列队尾的元素大于等于当前需要插入的数时，就可以把队尾删除
即维护了一个单调上升的单调队列
每次取出对头元素即为最小值 

解题代码：

#include <cstdio>
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
const int N = 300010;
 
int a[N];
LL s[N];
int q[N], hh, tt;
 
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    
    LL res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i ++ )
    {
        while (i - q[hh] > m) hh ++ ;//当队列中的元素数量多于m时弹出对头，
                                     //这里本应该是i - q[hh] + 1的但因为上次循环i加了一次所以需要少减一次
        res = max(res, s[i] - s[q[hh]]);//记录每次 循环的对最大值
        while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;//当队列不空切队尾元素大于s[i]时弹出队尾；
        q[++ tt] = i;//经过上面的while循环此时队列中的元素一定都小于i，将i插入队尾
    }
    
    cout << res << endl;
    
    return 0;
}