最大子序和

前置知识：单调队列

---

原题链接

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

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

输入格式

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

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

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

输出格式

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

数据范围

\(1≤n,m≤300000\)

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

---

思路

对于求一段连续的区间和问题，我们可以采用前缀和优化，然后暴力枚举各个子区间。时间复杂度为 \(O(n^2)\)。

采用枚举右端点的方法，来进行优化，可以使时间复杂度降至 \(O(n)\)。

状态定义 dp[i]

集合： 以 \(i\) 为右端点，长度不超过 \(m\) 的子区间的和的集合。

属性： 最大值。

状态计算： \(dp[i] = \max\{s[i]-s[j]\}_{(1\le i-j\le m)}\)

由上式可以得出 \(j\) 的范围：\(i-m\le j\le i-1\)。

因此状态计算可以转化为 \(dp[i] = s[i] - \min\{s[j]\}_{(i-m\le j\le i-1)}\)

接着，问题就转化为，求区间 \([i-m,i-1]\) 内的最小值，可以用滑动窗口来做到 \(O(n)\) 的时间维护。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 300010;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

    int hh = 0, tt = 0;
    int res = -0x3f3f3f3f;
    // 由于子序列的长度至少是1，设置答案为最小值，方便后续更新
    for (int i = 1; i <= n; i++) {
        if (i - m > q[hh]) hh++;    // 单调队列大于区间长度，弹出队头
        res = max(res, s[i] - s[q[hh]]);    // 更新答案
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;  // 线性维护单调队列
        q[++tt] = i;    // 放入队尾
    }

    cout << res << endl;

    return 0;
}