$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：以\ i\ 为右端点，长度不超过\ m\ 的连续子区间$
  $属性：\max$

• $2. 状态转移$
  $f_i=\max\{s_i-s_j\}\ (i-m\le j\le i-1)$
  $即，对于每一个\ s_i，找到一个\min\{s_j\}\ (i-m\le j\le i-1)，可用单调队列来维护$
  $因此，f_i=s_i-\min\{s_j\}\ (i-m\le j\le i-1)$
  $最后，res=\max\{f_i\}\ (1\le i\le n)$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 300010, INF = 0x3f3f3f3f;

int n,m;
int q[N],s[N];

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

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

    int res=-INF,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;
}