原始题目

下面这段代码横线处应该填什么？

int maxSubArray(int a[], int n) {
    int currentSum = a[0];
    int maxSum = a[0];
    for (int i = 1; i < n; i++) {
        currentSum = max(a[i], ___);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

• A. currentSum
• B. currentSum + a[i]
• C. maxSum + a[i]
• D. a[i]

答案：B（currentSum + a[i]）

完整写法（Kadane 算法，一维 DP）：

int maxSubArray(int a[], int n) {
    int currentSum = a[0];
    int maxSum = a[0];
    for (int i = 1; i < n; i++) {
        currentSum = max(a[i], currentSum + a[i]);  // 另起炉灶 vs 接着续
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

图解：另起炉灶还是接着续

以经典数据 {-2, 1, -3, 4, -1, 2, 1, -5, 4} 为例（绿色是最大子段，红点是“另起炉灶”的位置）：

状态含义

currentSum 表示以 i 结尾的最大子段和。到了第 i 个元素只有两种选择：

1. 另起炉灶：从 a[i] 重新开始（前面的和是累赘时）
2. 接着续：把 a[i] 接到前面的子段后面，即 currentSum + a[i]

两者取大。若 currentSum 为负，a[i] 单干必然更优——这就是「前面的和为负就果断丢弃」的贪心本质。

手动模拟

输出 6，对应子段 [4, -1, 2, 1]。

逐项排除

初始化：最容易踩的坑

int currentSum = a[0], maxSum = a[0];   // ✅ 正确
// int currentSum = 0, maxSum = 0;      // ❌ 全负数组会错

若初始化为 0，输入 {-3, -1, -2} 时会输出 0，而正确答案是 -1（题目要求子段非空）。循环也必须从 i = 1 开始。

复杂度

Kadane 只需一次线性扫描、两个变量，是 DP 入门必背模型。

考点总结（CSP-J/S 初赛、程序填空）

1. 见到 max(a[i], currentSum + a[i]) 结构 → 最大子段和 / Kadane。
2. currentSum 的定义必须带「以 i 结尾」，否则递推不成立。
3. 初始化用 a[0]，不能是 0（全负数组陷阱）。
4. 每步都要 maxSum = max(maxSum, currentSum)，答案在全局里取，不是最后的 currentSum。

思考题

数组 {-3, -1, -2} 用上面的代码跑出来是多少？如果题目要求「子段可以为空，空子段和为 0」，该改哪一行？