[Acwing] 135. 最大子序和 滑动窗口

前言

抽象出基础模型 传送门 :

思路

不超过 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>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