BISHI134. 最大子段和
题目描述
给定一个长度为 n 的整数数组 A。请你从中选取一个非空子数组， 使得其元素之和最大，求出这个最大和。 「子数组」指从原数组中连续选取一段元素（可以全部选取，也可以只选取一个）。
输入格式
输入共两行。第一行输入一个整数 n，代表数组的长度。 第二行输入 n 个整数 A[i]，代表数组元素。
输出格式
在一行上输出一个整数，代表所能得到的最大子数组元素和。
示例
示例 1
输入：
4
2 2 -3 2
输出：
4
说明：
最优子数组为前两个元素 [2, 2]，和为 4。
示例 2
输入：
4
2 -1 3 -1
输出：
4
说明：
最优子数组为 [2, -1, 3]，和为 4。
解题思路
第一步：理解问题本质
要在所有连续子数组里找和最大的那个。n 个元素的连续子数组共有 O(n²) 个，暴力枚举两端再求和是 O(n³)，即使加前缀和优化也还是 O(n²)。
第二步：暴力枚举
best = -inf
for i in range(n):
s = 0
for j in range(i, n):
s += A[j]
best = max(best, s)
O(n²)，能过小数据，但还有更好的办法。
第三步：Kadane 线性 DP（最优）
设 cur 为「以当前元素结尾的最大子数组和」。对每个新元素 x，只有两种选择：
- 另起一段：从 x 开始，和为
x； - 接在后面：把 x 接到以「前一个元素结尾的最优段」后面，和为
cur + x。
所以 cur = max(x, cur + x)，同时用 best 记录遍历过程中的最大值。
关键细节：题目要求非空，所以初值要取 A[0] 而不是 0。
如果数组全是负数，用 0 初始化会错误地返回 0（空子数组），
而正确答案是最大的那个负数。
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入
import sys
def solve() -> None:
"""Kadane 算法求最大子段和（非空）"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
arr = list(map(int, data[1:1 + n]))
best = cur = arr[0] # 非空：用首元素初始化
for x in arr[1:]:
cur = max(x, cur + x)
best = max(best, cur)
sys.stdout.write(str(best) + "\n")
if __name__ == "__main__":
solve()
示例推演
以 2 2 -3 2 为例：
| 处理 x | cur = max(x, cur+x) | best |
|---|---|---|
| 2（初始化） | 2 | 2 |
| 2 | max(2, 4) = 4 | 4 |
| -3 | max(-3, 1) = 1 | 4 |
| 2 | max(2, 3) = 3 | 4 |
best = 4，与答案一致。
再以全负数 -1 -2 -3 为例：cur 依次为 -1、max(-2,-3)=-2、max(-3,-5)=-3，
best = -1，正确返回最大的单个负数。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 小数据可用 |
| 前缀和 | O(n²) | O(n) | 略有优化 |
| Kadane | O(n) | O(1) | 推荐，最优 |
易错点总结
1. 允许空子数组导致返回 0
如果把初值设成 0，全负数数组会返回 0（空段），
但题目要求非空。用 arr[0] 初始化即可避免。
2. 把「子数组」当成「子序列」
子数组必须连续；子序列可以不连续。本题是连续，别做错。
3. 忘记考虑单元素
cur = max(x, cur + x) 保证任何时候都可以从 x 重新开始，
天然覆盖了「答案就是某一个元素」的情况。
扩展思考
- 如果允许空子数组，初值设为 0、
best = 0即可。 - 「最大子段积」不能直接套用，需要同时维护最大值和最小值（因为负数相乘会翻转）。
- 二维的最大子矩阵和可以按行压缩后套用 Kadane。