上次遇到相同的题，想到前缀和，却不会单调队列优化，我菜炸了~

所用知识：

• 前缀和：求一段区间的和
• 单调队列优化：滑动窗口

详情见注释啦

#include <iostream>

using namespace std;

const int N = 300010;

int n,m;
int s[N],q[N]; // s[]为前缀和 ， q[] 数组模拟队列，存的是a[]的下标

int main()
{
    cin >> n >> m;

    for(int i=1;i<=n;i++)
    {
        cin >> s[i];
        s[i] += s[i-1]; // 边读边处理前缀和
    }

    // 第一层境界：前缀和，显然会超时 过8/11 (也能得到大部分分了~~)
    //int res=-1e9;
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=i-m+1;j<=i && j >0 ;j++) res=max(res,s[i]-s[j-1]);
    // }

    // 第二层境界：单调队列优化(滑动窗口)
    int res=-1e9;
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(q[hh] < i - m) hh ++ ;  //  判断队头是否滑出窗口
        res=max(res,s[i] - s[q[hh]]);  //  队头存的一定是当前窗口的最小值
        while(hh <= tt && s[q[tt]] >= s[i]) tt -- ; // 单调队列优化核心语句！（“有更优秀的备胎来了~~”）
        q[++ tt] = i; // 把当前元素加入进来
    }

    cout<<res<<endl;

    return 0;
}