最大子序和

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

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

输入格式

第一行输入两个整数 n,m。

第二行输入 n 个数，代表长度为 n 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

1≤n,m≤300000

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

思路

对于固定m的可以直接用前缀和枚举求解, 而这里是不超过m, 故需要考虑更多情况。

先找到暴力枚举的顺序, 然后再进行优化。

这里可以枚举每个子序列的节点, 然后往前枚举所有长度不超过m的子序列, 利用前缀和来计算区间和。

根据计算公式 s[i] - s[j - 1], 显然想要求最大, 肯定要让s[i] 越大, s[j - 1] 越小越好。

而往前枚举所有长度不超过m的子序列时, 也就是枚举 s[j - 1], 即 s[i] 是确定, 那么问题就转化为：找一个区间内的最小值s[j - 1]。

可以使用单调队列优化。 res 在q入队之前更新是因为, $a[q[hh]]$ 需要是不包含i的最小值, 不然i有可能影响到, 最后变成$i-i=0$
同理, 这里队头出队的边界为$i-q[hh]>m,i-q[hh]$ 的区间长度包含 $[q[hh]+1,i]$为实际数量减一,如果按正常的单调队列, 这里应该用>= 表示$[q[hh],i]$超过$m$, 或者用$i-q[hh]+1>m$, 但因为求得是前缀和的$s[j-1]$, 故取值范围在$[i-m,i-1]$ , 其长度为$m$, 加上$i$的总长度为$m+1$, 即$i-q[hh]+1>m+1$, 优化一下为 $i-q[hh]>m$

代码

#include <iostream>
using namespace std;
const int N =3e5 + 10;
 
int n,m;
int hh,tt;
int q[N];
int a[N];
 
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    
    int res = -2e9;
    for(int i = 1; i <= n; i++)
    {
        while(q[hh] < i - m) hh++;
        res = max(res, a[i] - a[q[hh]]);
        while(hh <= tt && a[i] <= a[q[tt]]) tt--;
        q[++tt] = i;
    }
    
    cout << res << endl;
    return 0;
    
}