题意

给出一个整数序列，要求在所有连续且非空的子段中，找出和最大的那一段，并输出这个最大和。

思路

最直接的教学版做法是枚举所有连续子段：

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// brute.cpp：枚举所有连续子段求和，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n;
int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long ans = -(1LL << 60);
    for (int l = 1; l <= n; l++) {
        long long sum = 0;
        for (int r = l; r <= n; r++) {
            sum += a[r];
            ans = max(ans, sum);
        }
    }

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

但正式解法只要线性 DP。

设 dp[i] 表示以第 i 个元素结尾的最大子段和。

那么以 i 结尾的最优子段只有两种选择：

1. 只取 a[i]
2. 把 a[i] 接到前一个最优子段后面

因此转移是：

dp[i] = max(a[i], dp[i-1] + a[i])

最后对所有 dp[i] 取最大值就是答案。

DP 公式

设 $dp_i$ 表示以第 $i$ 个数结尾的最大连续子段和。初始化：

对 $i>1$ 有：

最终答案不是固定结尾，而是：

样例 [2,-4,3,-1,2,-4,3] 的状态如下：

每格只依赖前一格，所以 Python 正解把整张 dp 表压缩成变量 current。

公式解释：以 i 结尾的最优子段只有两种情况：从 i 重新开始，或者把 a_i 接到前一个结尾最优子段后面。对每个结尾算出最优值后，全局答案就是所有结尾里的最大值。

Python 知识

• 整数迭代器直接流过输入，不需要保存数组或 dp 列表。
• current = max(value, current + value) 与状态转移公式完全对应。
• 首项单独初始化，保证全负序列也必须选择非空子段。

代码

1
2
3
4
5
6
7
8
9
10import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
_ = next(data)
current = answer = next(data)
for value in data:
    current = max(value, current + value)
    answer = max(answer, current)
print(answer)

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$（不计输入缓冲）

总结

这题是最大子段和的经典模型。

关键在于把“全局最优子段”转成“以某位置结尾的最优子段”来做状态转移。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。