这道题是前缀和与单调队列的结合
先看题目：
题目要求小Z能得到的最大幸运值就相当于求在一段长度小于m的任意长度区间内，能得到的最大幸运值，如果全为正可直接用前缀和解决，只需要求出值最大的段区间的和就行，但这道题我们需要考虑负数的情况就要再加上单调递增队列
核心代码：
l=1,r=0; p[++r]=0; for(int i=1;i<=n;i++){ while(l<=r&&p[l]<i-m) l++; mx=max(mx,a[i]-a[p[l]]); while(l<=r&&a[p[r]]>=a[i]) r--; p[++r]=i; }因为段区间在[l,r]间，所以r-l-1<=m;可推出l>r-m
完整代码：
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define endl '\n' #define fi firse #define se second const ll N=1e6+10; ll l,r; ll p[N]; ll a[N]; void solve() { ll n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } a[0]=0; ll mx=-1e18; for(int i=1;i<=n;i++){ a[i]=a[i-1]+a[i]; } l=1;r=0; p[++r]=0; for(int i=1;i<=n;i++){ while(l<=r&&p[l]<i-m) l++; mx=max(mx,a[i]-a[p[l]]); while(l<=r&&a[p[r]]>=a[i]) r--; p[++r]=i; } cout<<mx; } signed main() { IOS; ll T=1; while(T--) solve(); return 0; }
