前言
抽象出基础模型
传送门 :
思路
不超过 m m m的区间范围,求最大的 s u m sum sum
显然我们可以统计前缀和
这样子对于一个区间 [ L , R ] [L,R] [L,R]的和就变成了 s u m [ R ] − s u m [ L ] sum[R]-sum[L] sum[R]−sum[L]
如果我们通过枚举 R ( 1 − i ) R(1-i) R(1−i) ,
通过题意我们可知 L ∈ [ R − m , R − 1 ] L \in [R-m,R-1] L∈[R−m,R−1]
显然问题可以转换为,在一个大小为 m m m的窗口内,找一个最小的 s u m [ i ] sum[i] sum[i]
因此问题就这样转换为滑动窗口了
CODE
const int N = 3e5+10;
ll s[N];
int n,m;
int q[N];
int hh,tt;
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]+= s[i-1];
}
ll ans = -0x3f3f3f3f;
/*
每次固定右端点
对于[R-M,R) 就变成了 ,在区间内找一个 最小的Sum[l]
使得sum[r] - sum[l] 最大
而维护区间内的最小值,我们可以使用单调队列优化,从而使得时间复杂度O(n*m) -> O(n)
*/
for(int i=1;i<=n;i++){
//如果队头 和 当前右端点 的长度超过了m
if(q[hh]<i-m) hh++;
ans = max(ans,s[i] - s[q[hh]]);
//如果比s[i]大了,那么我们就踢出去,好让s[i]进来
while(hh<=tt && s[q[tt]] >= s[i])
tt--;
q[++tt] = i ;
}
cout<<ans<<endl;
}
/**mYHeart is my algorithm**/
int main()
{
IOS
CIT
COT
//int t;cin>>t;while(t -- )
solve();
return 0;
}