算法竞赛进阶指南，58页，单调队列
本题要点：
1、长度最大值为m的滑动窗口内，所有数的和可以用 前缀和的差值来表示。
当右端点 i固定， 左边 i - m ~ i - 1 这m下标中，取值 k < j（i - m <= k < j <= i - 1）
如果 sum[k] <= s[j], 那么 sum[i] - sum[j] >= sum[i] - sum[k], j的生存时间比k长；
2、用一个队列来存 一个单调的前缀和的下标，（下标位置递增，前缀和也递增），
每一时刻，队头存放的 q[L] ,是当前 i 下标结尾的前缀和，应该减去的前缀和（这样减，得到以i结尾的滑动窗口所有数的最大和）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 300010;
int a[MaxN], s[MaxN]; // s[i] 表示前缀和
int q[MaxN * 2]; //单调队列
int n, m;int main()
{
scanf("%d%d", &n, &m);s[0] = 0;for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);s[i] = s[i - 1] + a[i];}int ans = -1e9;int L = 1, R = 1; //队列头和尾q[1] = 0;for(int i = 1; i <= n; ++i){
while(L <= R && q[L] < i - m) // 确保滑动窗口的元素个数最多有m个{
++L;}ans = max(ans, s[i] - s[q[L]]);while(L <= R && s[i] <= s[q[R]]) //确保单调性{
--R;}q[++R] = i;}printf("%d\n", ans);return 0;
}/* 6 4 1 -3 5 1 -2 3 *//* 7 */