数据结构优化dp是最骚的。。。

看到区间和，常用的技巧就是前缀和了。所以我们弄出一个前缀和数组b。

那么这个答案就能转化为\(max(a_i - a_j)\)。

我们每一次就只枚举i，那么这个max可以把\(a_i\)拿出来，也就是\(a_i - min(a_j)\)。

所以转换为区间最小值。直接转化为RMQ问题，使用ST表即可。

代码：

#include
    
     #include
     
      const int maxn = 500005;int a[maxn], n, m;int st[maxn][21];int ans = -0x3f3f3f3f;int query(int l, int r){    int k = 0;    while((1 << (k + 1)) <= r - l + 1) k++;    return std::min(st[l][k], st[r - (1 << k) + 1][k]);}int main(){    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);    for(int i = 1; i <= n; i++) a[i] += a[i - 1];    for(int i = 1; i <= n; i++) st[i][0] = a[i];    for(int j = 1; j <= 20; j++)    {        for(int i = 1; i + (1 << j) - 1 <= n; i++)        {            st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);        }    }    for(int i = 1; i <= n; i++)    {        int l = i - m;        if(l < 0) l = 0;        int temp = query(l, i);        ans = std::max(ans, a[i] - temp);    }    printf("%d\n", ans);    return 0;}