AcWing 135. 最大子序和（前缀和 + 单调队列求定长区间最小值）

前置知识：单调队列求滑动窗口最小值

题意：

给定一个 长度为 n 的整数序列（可能有 负数），从中 找出一段长度不超过 m 的连续子序列，使得 子序列中所有数的和 最大。n、m ≤ 3 * 10 ^ 5

思路：

根据我们的经验，计算 “区间和” 的问题，一般转化为 “两个前缀和相减” 的形式进行求解。

先求出 s[i] 表示序列里前 i 项的和，则 连续子序列 [L,R] 中数的和 就等于 s[R] - s[L - 1]。

那么 原问题可以转化为：找出 两个位置 x, y，使 s[y] - s[x] 最大，并且 y - x ≤ m。

既然将 前缀和数组 s 都求出来了，那么就很好办了：

• 枚举区间的 右端点 i ：从 i = 1 开始，依次从前往后枚举到 i = n。

• 对于 每一个右端点，固定好之后，我们找到一个 左端点 j，其中 j ∈ [i - m，i - 1] 并且使得 s[j] 最小（根据 任意一段区间[i，j + 1] 的元素和 等于 s[i] - s[j]，我们要 使区间和最大，显然要 使 s[j] 尽量小）。

上述的过程不就是一个在每一个 区间长度为 m 的区间 中找到 最小值 吗，最终，我们就将本题转化成了 滑动窗口的经典运用。

将 遍历每一个右端点求出来的最大区间和 求出来，并取 max，即为答案。

时间复杂度：

$O(n)$

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 3e5 + 10;
int a[N], q[N];
int n, m;
int s[N];

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

    return ans;
}

signed main()
{
    
    int T = 1; //cin >> T;

    while (T--)
    {
    
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
        {
    
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }

        cout << solve() << '\n';

    }

    return 0;
}