Kadane 算法：一行 DP 解决最大子数组和

一句话结论（30s）

Kadane 用一行 curSum = max(num, curSum + num) 把最大子数组和从 O(n²) 降到 O(n)，核心原因是一条贪心决策：当前缀和 curSum < 0 时它只会拖累后面的和，必须丢弃、重新从当前元素开始。

核心原理（2min）

状态：dp[i] = 以 nums[i] 结尾的最大子数组和；转移 dp[i] = max(nums[i], dp[i-1] + nums[i])。
curSum 就是 dp[i-1]，滚动变量把空间压到 O(1)。
关键判定：curSum + num < num 等价于 curSum < 0——负数前缀拖后腿就砍掉。为什么这样设计？ 因为”接前缀”还是”重新开始”这个二选一里，只要前缀和为负，接上它一定比不接更小，决策就退化成一句恒真判断，不需要试算两条路径。
环形扩展：跨边界的最大子数组 = 总和 - 最小子数组和，全负数时退回 maxSum（不能用 total - minSum，否则得到 0）。

底层深入（5-10min）

问题

给定整数数组，找具有最大和的连续子数组。有负数，所以不是”取全部正数”那么简单。

暴力：O(n²)

int maxSum = nums[0];
for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += nums[j];
        maxSum = Math.max(maxSum, sum);
    }
}

💭 思考：看到什么信号该放弃”枚举所有子数组”？——“连续子数组求最值”第一反应是双循环枚举起点终点（O(n²)），但题目一提到要 O(n)，就说明子数组之间肯定有可复用的重叠信息。注意到”以 i 结尾的子数组”和”以 i-1 结尾的子数组”只差一个 nums[i]，答案完全可以由前一个状态推出来——这一步”把答案绑定到结尾位置”就是 O(n²) 到 O(n) 的破题点。

Kadane 算法：O(n) 单遍历

int maxSum = nums[0], curSum = nums[0];
for (int i = 1; i < nums.length; i++) {
    curSum = Math.max(nums[i], curSum + nums[i]);
    maxSum = Math.max(maxSum, curSum);
}

核心决策：在位置 i，有两个选择——要么把 nums[i] 接到前面的子数组后面（curSum + nums[i]），要么丢弃前面的前缀重新开始（nums[i]）。

为什么负数前缀应该被丢弃？

curSum + nums[i] < nums[i] 等价于 curSum < 0。当前置子数组和为负数时，拼接它只会拖累当前位置的值——不如从头开始。

Kadane 的精髓：即使你的前缀是最好的数组，只要它的和是负数，就该丢弃它。

💭 思考：为什么 curSum < 0 这一条就够做决策？——在位置 i 只有两条路：接上前缀（curSum + nums[i]）或重头开始（nums[i]）。比较两者大小，curSum + nums[i] < nums[i] 移项就是 curSum < 0——也就是说”该不该接”根本不用看 nums[i] 是谁，只看前缀符号。把二选一化成一个恒成立的不等式判断，这就是 Kadane 能一行写出来的原因。

为什么会卡在 O(n²) 想不出优化？ 因为暴力法是在”枚举所有起点终点”里找最大，而我们真正该问的是”以 i 结尾的最大和是多少”——一旦把答案和”结尾位置”绑定，dp[i] 只依赖 dp[i-1]，一层循环就够。

DP 视角

dp[i] = 以 nums[i] 结尾的最大子数组和
dp[i] = max(nums[i], dp[i-1] + nums[i])

curSum 就是 dp[i-1]，空间优化到 O(1)。

扩展：环形数组的最大子数组和

环形数组：子数组可以跨越数组末尾和开头（有”首尾相连”）。最大子数组和可能取两种形式之一：

普通连续子数组（不跨越边界）→ Kadane 正常一次
跨越边界的子数组 = 总和 - 最小子数组和

int maxSubarraySumCircular(int[] nums) {
    int total = 0, maxSum = nums[0], curMax = 0;
    int minSum = nums[0], curMin = 0;
    
    for (int num : nums) {
        curMax = Math.max(curMax + num, num);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(curMin + num, num);
        minSum = Math.min(minSum, curMin);
        total += num;
    }
    
    return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    //                                                    ↑ 全负数时不能用 total-minSum
}

全负数时 total - minSum = 0 但数组全负 → 正确结果应是最接近零的那个负数（即 maxSum）。

💭 思考：环形数组为什么是 总和 - 最小子数组和？——跨边界的子数组，等价于”整圈里挖掉中间不取的一段”。想让”取的那段”最大，就等于让”挖掉的那段”最小，于是问题瞬间转换成”求最小子数组和”——这是 Kadane 的一个镜像，把 max 换成 min 即可。反过来全负数时 total - minSum 会挖空到 0（空子数组不合法），所以要用 maxSum 兜底。

章末提问

为什么 curSum < 0 就必须丢弃前缀，而不是继续累加等它变正？ 结论：因为负数前缀对后面任何元素都只有拖累作用，“接前缀”恒小于”从头开始”，继续等是徒劳；所以最优决策是无条件砍掉。
Kadane 里的 curSum 和 DP 的 dp[i] 是什么关系？ 结论：curSum 就是滚动变量版的 dp[i-1]，因为 dp[i] 只依赖 dp[i-1]，用一个变量滚动即可把空间从 O(n) 压到 O(1)。
环形数组为什么是 total - minSum，全负数时为什么不能用？ 结论：因为跨边界子数组等于”总和减去中间不取的那段最小子数组和”；但全负数时 total - minSum 会得到 0（一个不存在的空子数组），所以必须退回 maxSum 取最接近零的那个负数。

总结

Kadane 算法把”找最大子数组和”这个问题从 O(n²) 降到 O(n)，核心思想就是一行的贪心决策：curSum = max(num, curSum + num)。当 curSum < 0 时，前缀就该被丢弃——负数的积累只会让后面的和更小。

Kadane算法——最大子数组和的单遍历解法