原题

LeetCode 53. 最大子数组和（Maximum Subarray）
给定一个整数数组 `nums`，找出一个具有最大和的连续子数组，返回其最大和。

核心思路

这道题最高效的解法是 Kadane 算法，它用一层循环就能解决。代码虽短，背后的思想却极其精妙。它的核心策略可以浓缩为一句话：

一旦当前累积和 `sum` 变成负数，就立刻丢弃，从0重新开始。

这句话背后，其实是一个我们生活中也常做的决定：果断砍掉“负资产”，不被它拖累未来。

具体解释：一个股票交易的直觉

想象你正在连续几天进行股票交易，数组里的每个元素就是你当天的盈亏。你的目标是找到连续几天，让自己的总收益最大化。

 你会每天记录到目前为止的累积盈亏，这就是变量 `sum`。
 如果有一天你发现，前面这一连串操作算下来，不仅没赚钱，总账反而亏了（即 `sum < 0`），你会怎么做？

 最理性的选择就是：立刻清仓，就当之前那几天没发生过，从零开始。因为你心里清楚，拿着一个亏损的包袱往前走，只会抵消掉后面的盈利，让你赚得更少。

代码里的 `if (sum < 0) sum = 0;`，就是这个“清仓”动作的数学表达。

逻辑论证：为什么不从i和j的中间重新开始？

这是这个算法最容易被质疑的地方，也是理解它正确性的关键。

假设我们有一段前缀 `[i, j]`，它的总和 `sum` 第一次由正变负。有人会问：“你就这么把从 `i` 到 `j` 全扔了？万一从 `i` 和 `j` 的中间某个位置开始，能得到更大的和呢？”

答案是：绝对不可能。 我们可以用反证法来证明。

前提条件是：前缀 `[i, j]` 的总和 `< 0`，并且它是首次变负。这意味着什么？

1.  因为 `j` 是使总和首次变负的点，说明在 `j` 之前的所有前缀和（即从 `i` 到 `k`，其中 `i ≤ k < j`）都是非负的。
2.  现在，任意取一个从中间位置 `k+1` 开始的子数组，它的和可以看作：
    `总和([i, j]) = 总和([i, k]) + 总和([k+1, j])`
3.  既然 `总和([i, k]) ≥ 0`（来自第1点），那么我们从总和中把它减掉，剩下的部分只会更小或相等：
    `总和([k+1, j]) = 总和([i, j]) - 总和([i, k])`
4.  由于 `总和([i, j])` 是负数，减去一个非负数 `总和([i, k])`，结果 `总和([k+1, j])` **必然是一个更小的负数**。

这就意味着，任何一个从这个区间中间开始的子数组，都“亏得更惨”，远不如直接从 `j+1` 重新开始来得好。所以，当我们发现 `sum < 0` 时，可以放心地把这整个 `[i, j]` 区间连根拔起，一丢了之，绝不会错过最优解。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;                    // 当前累积和，从0开始
        int res = Integer.MIN_VALUE;    // 全局最大和，初始化为最小值以处理全负数数组
        for (int x : nums) {
            sum += x;                   // 累加当前元素
            res = Math.max(res, sum);   // 每走一步，都尝试刷新历史最高收益
            if (sum < 0) {              // 一旦发现当前累积和变成了“负资产”
                sum = 0;                // 立刻清仓，从0重新开始
            }
        }
        return res;
    }
}

总结

Kadane 算法的精妙之处在于，它将一个看似需要回溯的问题，通过“动态放弃”的贪心思想，简化成了 O(n) 的一次遍历。它告诉我们：及时止损，不让过去的亏损绑架你的未来，才是获得全局最优解的唯一途径。 这不单是算法的智慧，也是一种生活哲学。