题解 |

用单调队列存范围内最小的前缀和，从前往后遍历更新值和单调队列即可

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=3e5+5;
using namespace std;

ll n,m;
ll a[maxn];
ll fro[maxn];
ll ans=-1e12;
ll que[maxn];

int main(){
ll i,j;

cin>>n>>m;
for(i=1;i<=n;i++)
{
    scanf("%lld",&a[i]);
    fro[i]=fro[i-1]+a[i];
}
ll l=0,r=-1;
que[++r]=0;

for(i=1;i<=n;i++)
{
    while(l<=r&&i-que[l]>m) l++;
    if(l<=r)    ans=max(ans,fro[i]-fro[que[l]]);
    while(l<=r&&fro[i]<=fro[que[r]]) r--;
    que[++r]=i;
}

printf("%lld\n",ans);
    
}