题目

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

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

输入格式

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

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

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

输出格式

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

数据范围

$1≤n,m≤300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

暴力解法

f(i, j)
- 集合： 以 a[i] 为结尾的长度不超过 j 的所有连续子序列
- 属性： 序列元素和 a[i-j+1] + a[i-j+2] + ... + a[i]，可以用前缀和来求解 s[i] - s[i-j], j = 1, 2, ..., m

目标：求对于 i 和 j 的所有合法取值，得到的结果的最大值

#include <iostream>

using namesapce std；

const int N = 3e6 + 10

int s[N], n, m;

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    int res = 0x8f8f8f8f;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (i >= j) 
                res = max(res, s[i] - s[i - j]);

    cout << res << endl;

    return 0;
}

时间复杂度 $n*m \sim 10^{11}$ 会超时

单调队列优化

目标是s[i] - s[i-j], j = 1, 2, ..., m 的最大值，等价于求 s[i-j], j = 1, 2, ..., m 的最小值，即 s 的下标取区间 [i-m, i-1] 内的最小值，即滑动窗口求最小值问题，可以用单调队列来优化。y 老师的代码与基础课的代码不大一样，实际上是把第一轮循环的更新操作放到循环之前去了，所以看起来有一点费解，这里给出一个与基础课对应的版本。

#include <iostream>

using namespace std;

const int N = 3e5 + 10;

int s[N], q[N], hh, tt;
int n, m;

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    int res = 0x8f8f8f8f;

    hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++)
    {
        if (tt >= hh && i - m > q[hh]) hh ++;
        while (tt >= hh && s[q[tt]] >= s[i - 1]) tt --;
        q[++ tt] = i - 1;
        res = max(res, s[i] - s[q[hh]]);
    }

    cout << res << endl;

    return 0;
}