最大子序和：双向队列维护一个上升序列

最大子序和

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

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

输入格式
第一行输入两个整数n,m。
第二行输入n个数，代表长度为n的整数序列。
同一行数之间用空格隔开。

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

数据范围
1≤n,m≤300000
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

题目不难，我们容易想到暴力枚举，其时间复杂度是O(n * m)的这显然是不可取的。
再后我们容易想到用前缀和来枚举暴力做法。
于是我们有了下面的推断。将距离小于等于m的一系列前缀和拿出。

我们容易想到，这里面的最大值一定是：最小的减去最大的，当然还要同时满足最小的在最大的前面。
我们再想一想。这假设上述的条件满足。
这两个数之间有一个数是有一个数是大于或者等于这个最大值的，那么这里就矛盾了。最大的差值一定不可能是这两个，因为前面已经找到更大的数对了，所以我们可以维护一个区间队列，这个区间队列是升序的。

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
ll s[N], n, m;
int q[N];
int main() {
    scanf("%lld %lld", &n, &m);
    ll temp;
    s[0] = 0;
    for(ll i = 1; i <= n; i++) {
        scanf("%lld", &temp);
        s[i] = s[i - 1] + temp;
    }
    int h = 0, t = 0;
    ll ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++) {
        if(i - q[h] > m)    h++;
        ans = max(ans, s[i] - s[q[h]]);
        while(h <= t && s[q[t]] >= s[i]) t--;//这里保证队列区间里的数是上升的。如果不是上升，从队尾删除元素。知道上升为止。
        q[++t] = i;
        // printf("%lld\n", ans);
    }
    printf("%lld", ans);
    return 0;
}