最大子序和

一句话算法

长度受限的最大子段和，就是固定右端点时，在合法左端点里找最小前缀和。

问题模型

给定序列 $a_1,a_2,\ldots,a_n$ 和长度限制 $m$，求长度不超过 $m$ 的连续子段最大和。

设前缀和为：

区间 $(j+1,i)$ 的和为：

当右端点为 $i$ 时，左端点前缀下标 $j$ 必须满足：

所以要最大化 $S_i-S_j$，只需要在这个范围里找最小的 $S_j$。

核心直觉

右端点 $i$ 从左到右移动时，合法的 $j$ 范围也是一个滑动窗口：

[i-m, i-1]

我们维护这个窗口里的最小前缀和下标，队头就是当前最优左端点。

算法步骤

1. 预处理前缀和 S[0..n]，其中 S[0]=0。

2. 用单调队列维护候选前缀下标 j。

3. 初始把 0 入队，表示子段可以从第 1 个元素开始。

4. 从左到右枚举右端点 i。

5. 删除所有不满足 j >= i-m 的过期队头。

6. 用队头更新答案：

   $$ans=\max(ans,S_i-S_{q.front()})$$

7. 将当前前缀下标 i 加入队列前，弹出所有 S[q.back()] >= S_i 的下标，保持前缀和递增。

8. 把 i 加入队尾，继续处理下一个右端点。

算法证明

核心不变量： 处理右端点 $i$ 时，队列中保存的是所有仍合法、且可能成为最小前缀和的下标。

1. 合法性。 子段长度不超过 $m$，所以左端点前缀下标必须满足 $j\ge i-m$。每次先删除过期队头，队列中的下标都合法。
2. 最优性。 对固定右端点 $i$，$S_i$ 已确定。要最大化 $S_i-S_j$，只需要让 $S_j$ 最小。
3. 单调性。 若 j<i 且 S[j] >= S[i]，那么 j 更早过期，前缀和还不更小，以后不可能比 i 更优，可以删除。
4. 队头正确。 队列按前缀和值递增，队头就是当前合法范围内最小的前缀和下标。

因此每个右端点的最优子段都会被正确统计，所有右端点取最大值就是答案。

复杂度分析

每个前缀下标最多入队一次、出队一次。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$，若只看队列规模为 $O(m)$。

代码实现

        
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

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

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

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    long long ans = LLONG_MIN;
    deque<int> q;
    q.push_back(0);

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() < i - m) {
            q.pop_front();
        }

        ans = max(ans, prefix[i] - prefix[q.front()]);

        while (!q.empty() && prefix[q.back()] >= prefix[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }

    cout << ans << "\n";
    return 0;
}
    

        
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

        # 单调队列 + 前缀和：求长度不超过 m 的最大子段和。
# a 为 1 下标（a[0] 占位不用），要求 n >= 1 且 m >= 1；此时答案一定存在（至少取一个元素）。
# prefix[i] = a[1] + ... + a[i]，子段 (j, i] 的和 = prefix[i] - prefix[j]。
# 固定右端 i 时，只需在 j ∈ [i-m, i-1] 里找最小的 prefix[j]，故用递增单调队列维护该窗口最小值。
# C++ 用 long long 防前缀和溢出 int；Python int 任意精度，该坑不存在。

from collections import deque

type Arr = list[int]  # 1 下标数组，a[0] / prefix[0] 占位不用


def max_subarray_sum(a: Arr, m: int) -> int:
    """返回长度 <= m 的非空子段最大和。调用示例：max_subarray_sum([0, 2, -1, 3], 2) -> 3"""
    n = len(a) - 1

    # prefix 同样 1 下标；prefix[0] = 0 作为空前缀哨兵。
    prefix: Arr = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + a[i]

    # n >= 1 时子段 (0, 1] 一定合法（m >= 1），用它当初始答案，
    # 避免像 C++ 那样用 LLONG_MIN 哨兵（Python 无固定下界）。
    answer = prefix[1] - prefix[0]
    q: deque[int] = deque([0])

    for i in range(1, n + 1):
        # 合法左端点 j 需满足 i - j <= m，即 j >= i - m。
        while q and q[0] < i - m:
            q.popleft()

        best = prefix[i] - prefix[q[0]]
        if best > answer:
            answer = best

        # 队尾 prefix 不小于 prefix[i] 的，作为左端点不如 i 优，弹出。
        while q and prefix[q[-1]] >= prefix[i]:
            q.pop()
        q.append(i)

    return answer
    

测试用例

输入：

6 3
1 -2 3 5 -1 2

输出：

8

解释：长度不超过 3 的最大子段是 3 5，和为 8。

经典例题

1. AcWing 135

最大子序和模板题。重点是把“长度不超过 $m$”变成前缀和下标窗口。

2. luogu-P1714

同一模型。枚举右端点，单调队列维护合法范围内的最小前缀和。

应用分类详解

长度受限最大子序和的本质是：固定右端点后，在一个滑动范围内找最小前缀和。

一、长度受限区间和

• 典型模式： 连续子段长度不能超过或必须落在某个范围内，要求最大和或最小和。
• 识别信号： 出现“长度不超过 $m$”“连续子段”“最大区间和”。
• 核心建模： 区间和写成 $S_i-S_j$，右端点固定时维护合法 $j$ 的最小前缀和。

二、前缀和差值优化

• 典型模式： 目标可以写成当前值减去历史最优值。
• 识别信号： 式子形如 current - min(previous)，且 previous 的范围随当前位置单调移动。
• 核心建模： 用单调队列维护历史候选中的最小值或最大值。