【题解】长度不超过 m 的最大子序列和（前缀和 + 最小前缀维护） 审核通过

🧩 题意解析

给定一个长度为 n 的整数序列。
从中选出 任意长度 ≤ m 的连续子序列，使得它们的 元素之和最大。

等价于求：

max( sum(l..r) )，其中 r - l + 1 ≤ m

也就是：

max( s[r] - s[l] )，其中 0 ≤ r - l ≤ m - 1

其中 s[i] 是前缀和。

🔍 问题转化

令：

sum(l..r) = s[r] - s[l - 1]

如果 r 固定，要让区间和最大，就需要：

s[l - 1] 尽可能小 且 (l - 1) ∈ [r - m, r - 1]

也就是说：

我们需要维护“滑动窗口中最小前缀和”。

窗口范围：

前缀下标 ∈ [r - m, r - 1]

因为 i 表示 r，我们要找满足：

i - m ≤ pos ≤ i - 1

的最小前缀和。

🚀 如何维护窗口内前缀和最小值？

用 小根堆（priority_queue） 存储如下元素：

{前缀和 s[pos], 位置 pos}

每次 i 增大时：

• 把 (s[i], i) 压入堆作为候选
• 不合条件的（pos < i − m）弹出
• 当前合法窗口里的 最小前缀和 = 堆顶

每次计算最大区间和：

ans = max(ans, s[i] - min_prefix)

算法复杂度：

O(n log n)

完全能通过数据范围。

🧠 正确性说明

区间 (l..r) 长度 ≤ m
等价于：

r - (l - 1) ≤ m → (l - 1) ≥ r - m

因此我们必须在合法区间内选 s[l − 1] 的最小值，这恰是堆维护的内容。

由于每个前缀和只入堆一次、最多出堆一次，因此整体复杂度保证。

✅ AC 代码（可直接使用）

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 300010;
int s[N];

struct Node {
    int val, pos;
    bool operator<(const Node& a) const { return val > a.val; }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    priority_queue<Node> pq;
    pq.push({ 0, 0 });

    int ans = -0x3f3f3f3f;

    for (int i = 1; i <= n; i++) {
        while (!pq.empty() && pq.top().pos < i - m) pq.pop();
        ans = max(ans, s[i] - pq.top().val);

        pq.push({ s[i], i });
    }

    printf("%d\n", ans);
    return 0;
}