首先，很简单的dp方程：

\[f_i=max(s_i-s_j)(j\in [i-m,i])\]然后发现\(s_i\)与\(j\)无关，可以提出来：

\[f_i=s_i-min(s_j)(j\in [i-m,i])\]发现这个方程可以用数据结构优化，比如线段树，树状数组等等，我这里推荐用st表。

预处理：\(O(nlogn)\) 递推：\(O(n)\)

代码：

#include
    
     #define ll long longusing namespace std;inline int read(){    int x=0;char ch=' ';int f=1;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')f=-1,ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x*f;}int n,m;int a[500001];int s[500001];int st[20][500001];inline int query(int l,int r){    int k=log(r-l+1)/log(2);    return min(st[k][l],st[k][r-(1<
     
      >1]+1;    }    n=read();m=read();    for(int i=1;i<=n;i++){        a[i]=read();        s[i]=s[i-1]+a[i];        st[0][i]=s[i];    }    for(int k=1;k<=19;++k){        for(int i=1;i+(1<
      
       <=n;++i){            st[k][i]=min(st[k-1][i],st[k-1][i+(1<<(k-1))]);        }    }    int ans=-0x7fffffff;    for(int i=1;i<=n;++i){        int l=i-m;        if(l<0)l=0;        int num=s[i]-query(l,i);        ans=max(ans,num);    }    printf("%d",ans);    return 0;}