形式化题目

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$ 和整数 $m$，要求选出一段连续子段 $a_{l..r}$（$1 \leqslant l \leqslant r \leqslant n$），满足长度 $r - l + 1 \leqslant m$，最大化子段和 $\sum_{k=l}^{r} a_k$，输出这个最大值。子段长度至少为 $1$，元素可能为负。

样例：1 -3 5 1 -2 3，$m=4$，最优子段是 [5, 1, -2, 3]，和为 $7$。

暴力解法

思路

最直接的做法：枚举右端点 $r$，再枚举左端点 $l$，用前缀和 $O(1)$ 算出每个子段的和，取最大值。

更具体地，设前缀和 $s_0 = 0$，$s_j = a_1 + a_2 + \cdots + a_j$，那么子段 $a_{l..r}$ 的和就是 $s_r - s_{l-1}$。长度不超过 $m$ 的限制写成下标语言就是 $r - (l-1) \leqslant m$。于是：

其中 $i = l-1$。如果对每个 $r$ 都把窗口里的 $m$ 个 $s_i$ 扫一遍求最小值，总时间 $O(nm)$。$n = m = 3 \times 10^5$ 时约 $9 \times 10^{10}$ 次运算，必然超时。

复杂度

时间 $O(nm)$，空间 $O(n)$（前缀和数组）。

代码

暴力代码本文不单独给出：它只是推导的台阶，正式提交代码见下方正解的 main.py。

瓶颈

枚举右端点 $r$ 无法避免，但内层「在滑动窗口 $[r-m, r-1]$ 内找 $s_i$ 的最小值」被重复做了 $n$ 次。窗口每次只滑动一格：新下标 $r-1$ 进来，旧下标 $r-m-1$ 出去。这种「滑动窗口最值」正是单调队列的拿手好戏——不必每次重新扫描整个窗口。

正解

思路

沿用上面的式子，对每个右端点 $r$ 用单调队列维护窗口 $[r-m, r-1]$ 内前缀和最小的下标：

1. 队列里存的是下标 $i$，从队头到队尾下标严格递增，对应的 $s_i$ 值也严格递增。这样队头永远是窗口内 $s$ 最小的下标。
2. 计算右端点 $r$ 的答案前，先检查队头：若队头下标 $< r - m$，它对应的子段长度超过 $m$，从队头弹出（可能连续弹多次，不过每个下标一生只被弹一次）。
3. 用队头更新答案：$\text{answer} = \max(\text{answer},\ s_r - s_{\text{队头}})$。
4. 把 $r$ 入队前，从队尾弹出所有满足 $s_i \geqslant s_r$ 的下标。原因：这些下标比 $r$ 靠左（更早滑出窗口），前缀和又不比 $s_r$ 小——论「值小」比不过 $s_r$，论「活得久」也活不过 $r$，后续任何窗口都轮不到它当最小值，可以安全丢弃。
5. 初始时把 $i = 0$（即 $s_0 = 0$）放进队列，覆盖 $r = 1$ 时「窗口里只有 $s_0$」的情况。

每个下标恰好入队一次、出队至多一次，主循环均摊 $O(1)$，总复杂度 $O(n)$。

下面用样例 1 -3 5 1 -2 3（$m = 4$）推演一遍。前缀和 $s = [0, 1, -2, 3, 4, 2, 5]$；按代码顺序，每轮先查队头、再取答案、最后队尾弹出并入队 $r$：

观察重点：每一行「队尾弹出与入队」里，被弹出的都是「值不更小、还更早过期」的下标——$r=2$ 时 $s_2=-2$ 一口气把比它大且更早的 0 和 1 全部顶掉。到 $r=6$ 时队列剩 [2, 5]，对应 $s$ 值 $-2, 2$ 严格递增，队头 $s_2 = -2$ 正是最优左端点，$5 - (-2) = 7$ 与样例输出一致。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:16
# update_at: 2026-10-01 11:16

import sys
from collections import deque
from itertools import accumulate


def max_subsum_within(pre: list[int], m: int) -> int:
    """长度不超过 m 的连续子段的最大和：枚举右端点 j，单调队列给出 [j-m, j-1] 内的最小前缀和。"""
    queue: deque[int] = deque([0])  # 存前缀和下标，队头到队尾的值严格递增，队头即窗口内最小值
    best = pre[1] - pre[0]          # 子段长度至少为 1，先用第一个数兜底
    for j in range(1, len(pre)):
        while queue[0] < j - m:     # 队头下标太老，对应子段长度超过 m
            queue.popleft()
        best = max(best, pre[j] - pre[queue[0]])
        while queue and pre[queue[-1]] >= pre[j]:  # 不比 pre[j] 小的下标永远当不了后面的最小值
            queue.pop()
        queue.append(j)
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)
    nums = [next(data) for _ in range(n)]

    pre = [0, *accumulate(nums)]  # 前缀和：pre[j] - pre[i] 即子段 a[i+1..j] 的和
    print(max_subsum_within(pre, m))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:13
 * update_at: 2026-10-06 15:13
 */
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 300005;

ll pre[MAXN];   // pre[i] = a[1] + ... + a[i]，前缀和，pre[0] = 0
int q[MAXN];    // 单调队列，存前缀和下标；队头到队尾 pre 值严格递增
int head, tail; // 队列区间为 [head, tail)

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

    for (int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        pre[i] = pre[i - 1] + x;
    }

    ll ans = pre[1] - pre[0]; // 子段长度至少为 1，先用 a[1] 兜底
    head = 0;
    tail = 0;
    q[tail++] = 0; // 初始把 i = 0（pre[0] = 0）放进窗口

    for (int r = 1; r <= n; r++) {
        // 队头下标太老，对应子段长度超过 m，弹出
        while (head < tail && q[head] < r - m) {
            head++;
        }
        // 队头即窗口 [r-m, r-1] 内最小前缀和的下标
        ll cur = pre[r] - pre[q[head]];
        if (cur > ans) {
            ans = cur;
        }
        // 队尾那些前缀和不比 pre[r] 小、又更早过期的下标再也没用，弹出
        while (head < tail && pre[q[tail - 1]] >= pre[r]) {
            tail--;
        }
        q[tail++] = r;
    }

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

复杂度

• 时间 $O(n)$：每个下标入队、出队各至多一次；前缀和 $O(n)$。
• 空间 $O(n)$：前缀和数组与单调队列。
• 实测 $n = 292332$ 的最大数据点：约 $0.07\,\mathrm{s}$、峰值内存约 $40\,\mathrm{MB}$，远小于 $1\,\mathrm{s} / 128\,\mathrm{MB}$ 限制（Python 侧无 TLE/MLE 风险）。

总结

• 本题是「带长度上限的最大子段和」：把子段和写成前缀和之差 $s_j - s_i$ 后，长度限制变成窗口约束 $j - m \leqslant i < j$。
• 固定右端点 $j$ 时只需窗口内的最小前缀和，这是标准的滑动窗口最值问题，用单调队列把内层枚举从 $m$ 次降到均摊 $O(1)$ 次。
• 两个易错点：子段长度至少为 $1$（不能输出 $0$）；全负序列的答案是最大的单个元素，单调队列做法天然处理。
• 复杂度 $O(n)$ 时间、$O(n)$ 空间，$n = 3 \times 10^5$ 轻松通过。