最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划
题目描述
给定一个长度为 $n$ 的序列 $a$，找出其中 元素总和最大 且 长度 不超过 $m$ 的 连续子区间
分析
看到求一段 连续区间 的和的问题，会想到用 前缀和 进行优化，然后就是 枚举 区间的问题
暴力枚举 子区间是一种方法，但没有优化空间；因此不妨 枚举 子区间的 右端点
闫氏DP分析法
状态表示-集合 $f_i$：以 $i$ 为 右端点，长度 不超过 $m$ 连续子区间
状态表示-属性 $f_i$：区间的总和最大 $Max$
状态计算 $f_i$：
$$ f_i = \max\big\{{ s_i - s_j }\big\} \qquad (1 \le i - j \le m) $$
观察这个转移方程，首先这里的 $j$ 是有范围的：$i - m \le j \le i - 1 $
其次，$s_i$ 作为一个常量，可以提到外面去：$f_i = s_i - \min\big\{{ s_j }\big\} \qquad(1 \le i - j \le m)$
从前向后 维护一个长度不超过 $m$ 的区间的 最小值，就想到我们最熟悉的 滑动窗口模型 了
那么该状态 转移方程 就可以用 单调队列 进行优化了（你要是想线段树，树状数组搞搞也不是不行）
如何在 队头 维护一个 最小值 的 单增队列，请移步 算法基础课 学习，本题解不会讲解
Code
时间复杂度： $O(n)$ （每个元素至多入队出队一次，每次转移又是 $O(1)$ 的）
为了避免这个 高亮BUG，单调队列 q[] 改名为 que[] 了
由于这里 f[i] 没有相互依赖的关系，最后答案是统计所有 f[i] 的最大值
故我们直接用一个变量 res 来计算
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, m;
LL s[N], que[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]), s[i] += s[i - 1];
LL res = -1e18;
int hh = 0, tt = 0; que[0] = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && i - que[hh] > m) hh ++ ;
res = max(res, s[i] - s[que[hh]]);
while (hh <= tt && s[que[tt]] >= s[i]) tt -- ;
que[ ++ tt] = i;
}
printf("%lld\n", res);
return 0;
}
i - que[hh] > m这里怎么理解？我想的是
i-que[hh]+1>=m,`i-que[hh]+1表示长度，感觉很合理啊…获得[a,b]的写法是s[b]-s[a-1]而非s[a]
因为这里窗口存储的是前缀和数组的下标，而计算区间和时将两个前缀和s[i],s[j]相减后，实际求得的是原数组中区间长度为 i-j的子数组，而不是i-j+1
/*
举个栗子：i=10,m=3 则应该是
(1)m=3 ->8 9 10 a[8]+a[9]+a[10]=s[10]-s[7]
(2)m=2 ->9 10 a[9]+a[10]=s[10]-s[8]
(3)m=1 ->10 a[10]=s[10]-s[9]
由于当前遍历到的是i=10,所以s[10]是固定值，变化的是后面的s[j], i-m<=j<=i-1
我们在计算以10为终点的区间最大和时，队列中存入的应该是 7,8,9的索引号
想要求最大值，就转化为求s[j]的最小值
状态表示： s[i]-min(s[i-1],s[i-2],…,s[i-m])
其中最小值的下标记录在维护好的单调队列队头中！
https://www.cnblogs.com/littlehb/p/15801560.html
因为：que[j]的范围在[i-m,i-1]上，i-que[j]的范围应该在[1,m]上面，当i-que[j]>m时，说明que[j]这个值应该淘汰。
为什么先插入s[i],再取res=max不行
因为把s[i]加到队列里后可能会把之前的最小值弹出，自己变成最小值了，会丢掉之前m长度的最小值记录
下标范围不包括
i本身tt 为啥不是 -1 了？
因为插入了一个前缀和标杆0，不加0的话，如果第一个元素能取到的情况下，每次都取不到，模拟下就能明白，因为减的是s[l - 1]
因为求的是i之前，不包括i的长度为m的滑动窗口的最小值，在前m个元素为正值时，s[i]递增，这时窗口内最小值为s[0]，表示取1~i个元素求和，所以s[0]应当为第一个元素。这也是为什么先判断队头是否出队，接着取max再将i元素入队的原因（正常是，先将i入队，再判断队头是否出队）。
正常不也因该先i是否能成为最大值或最小值将t–；再进行i入队吗
如有不对还请指出
哈哈，是我写错了，谢谢纠正
为什么是s[i] - s[q[hh]]呢，前缀和求[q[hh] ~ i]求这个区间里的和，不应该是s[i] - s[q[hh]-1]吗，求大佬解惑
维护的不是区间的左端点，是区间左端点减1到i-1，是维护的j-1那个数组
妙
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
int n, m;
int const N=3e5 + 10;
long long sum[N],a[N],dp[N];
long long res= INT_MIN;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
dp[i]= INT_MIN;
}
for (int i = m; i <= n; i ){
for (int j = i - m; j <= i - 1; j++) {
dp[i] = max(dp[i], sum[i] - sum[j]);
}
}分享一下暴力解法虽然超时了但是可以过11/14的数据，思路挺简单的
双重循环的遍历是有点问题，前m个数的前缀和是遍历不到的，比如m=4,那sum[3],sum[2],sum[1]都遍历不到，如果前三个数恰好是正数，其他数都是负数，那答案本身就出问题了
感谢提的意见，确实是这样的，看来是我误打误撞混分混到了
s[que[tt]] >= s[i]，为什么是前缀和的s 来比较
我们维护的的单调队列里面相当于s[l-1]的值，想要求得和最大，就要使队头元素是最小这样才s[r]-s[l-1]得到最大值，如果区间里面的元素大于队头那么直接删除大于他的，如果里面元素比他小他可能在前面元素出队后成为最小就不用删除他前面的数
搞了半天贪心，原来是个dp
Orz
厉害！！