最大连续子数组：动态规划解法

给定数组 $A[1..n]$，找一段非空连续区间，使其中元素之和最大。困难不在于计算某段的和，而在于候选区间有 $Theta(n^2)$ 个。

1. 先把问题问得更具体

直接定义“前 $i$ 个数中的最优答案”，很难仅凭它推出第 $i+1$ 步。更有用的状态是：

$$f[i]=\text{必须以 }A[i]\text{ 结尾的最大连续子数组和}.$$

以 $i$ 结尾的最优区间只有两种来源：

• 把 $A[i]$ 接到以 $i-1$ 结尾的最优区间后面；
• 前面的和已经成为负担，从 $A[i]$ 重新开始。

所以

$$f[i]=\max\{A[i],\ f[i-1]+A[i]\}.$$

最终答案不是 $f[n]$，因为最优区间未必以最后一个位置结尾，而是

$$\max_{1\le i\le n}f[i].$$

2. Kadane 算法

状态只依赖上一项，可以把空间压成两个变量：

ending = A[1]
answer = A[1]
for i = 2..n:
    ending = max(A[i], ending + A[i])
    answer = max(answer, ending)

时间复杂度为 $O(n)$，额外空间为 $O(1)$。

3. 一个完整例子

对数组

$$[1,-2,4,5,-2,8]$$

$f$ 依次为

$$[1,-1,4,9,7,15].$$

到元素 4 时，与此前和 $-1$ 相接只会变差，于是重新开始；后面则一直保留这段，答案为区间 $[4,5,-2,8]$，和为 15。

4. 为什么局部重启不会错

若以 $i-1$ 结尾的最佳和小于 0，那么任何包含它、又以 $i$ 结尾的区间，都不如直接从 $A[i]$ 开始。丢掉负前缀不会损失最优解。

这不是“看到负数就切断”。例如 $[5,-2,4]$ 中间虽然出现负数，但累计和仍为正，保留它才能得到 7。真正判断的是此前整段的最优结尾和是否为负。

5. 恢复左右端点

维护当前候选段起点 candidateLeft：

• 若选择单独的 $A[i]$，令 candidateLeft = i；
• 若 ending 刷新全局答案，就记录当前起点和右端点 $i$。

相等时应先约定需要哪种答案，例如最短区间、最靠左区间或任意一组，否则不同实现可能返回不同但同样正确的区间。

6. 全负数组的边界

题目要求非空区间时，必须用 $A[1]$ 初始化。若用 0 初始化，数组 $[-5,-2,-7]$ 会错误返回空区间和 0；正确答案应是 $[-2]$，和为 $-2$。

只有题目明确允许空区间时，才可以把答案下界设为 0。

7. 与分治算法的关系

分治解法按中点把最优区间分为左侧、右侧、跨中点三种，复杂度 $O(n\log n)$；动态规划从左到右记录“以当前位置结尾”的必要历史，得到 $O(n)$。

两者都利用最优子结构，但切分问题的方式不同：分治按空间区间切，动态规划按扫描进度切。考试若要求写分治，不应只给 Kadane；若只求最优复杂度，Kadane 更直接。