单调队列

单调性的原理可以用一句没有啥道理的但又有点道理的话理解：如果一个人比你小还比你强，你就永远打不过他了。

最大子序和

输入一个长度为 \(n\) 的整数序列，从中找出一段长度不超过 \(m\) 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 \(1\)。

转换成前缀和
选取区间\([x+1,y]\) 和是 \(s[y]-s[x]\) 最大且 \(y-x \le m\)

对于一个 \(y\)
\(x \in [y- m, y-1]\) 所以 \(s[x]\) 越小越好

如果一个后进队的元素 \(s[x]\) 比前面的 \(s[?]\) 更小，则他一定比前面那个元素更优

所以选取的策略是：下标位置递增，对应的前缀和也是递增
维护队列即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std ;

const int N = 300010 ;

int n, m, ans ;
int a[N], s[N], q[N] ;

int main() {
	scanf("%d%d", &n, &m) ;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]) ;
		s[i] = s[i - 1] + a[i] ;
	}  
	int l = 1, r = 1 ; q[l] = 0 ;
	for (int i = 1; i <= n; i++) {
		while (l <= r && i - q[l] > m) l++ ;
		ans = max(ans, s[i] - s[q[l]]) ;
		while (l <= r && s[q[r]] >= s[i]) r-- ;
		q[++r] = i ;
	}
	printf("%d\n", ans) ;
}