单调队列维护区间最值

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
typedef long long LL;
#define pb push_back
#define F(i,a,b) for(int i=a;i<=b;i++)
#define dF(i,b,a) for(int i = b;i>=a;i--)
int n,m,st = 1,ed = 0,a[N],q[N];
LL ans = -3e9,s[N];
int main()
{
    cin>>n>>m;
    F(i,1,n)
    {
        cin>>a[i];
        s[i] = s[i-1]+a[i];
    }
    // max{s[i]-s[j]} i-m<=j<i
    // s[i]-min{s[j]} max(i-m,0)<=j<i
    F(i,0,n)
    {
        while(st <= ed && q[st] < i-m) st++;
        if(st <= ed) ans = max(ans,s[i]-s[q[st]]);
        while(st <= ed && s[q[ed]] >= s[i]) ed--;
        q[++ed] = i;
    }
    cout << ans << '\n';
    return 0;
}