LeetCode Hot 100 | 13. 最大子数组和

LeetCode 53. 最大子数组和 (Maximum Subarray)

1. 核心思路：动态规划 (Dynamic Programming)

状态定义 ($DP$ State)：

这一题最关键的点在于理解 $dp[i]$ 的含义。

• 误区：$dp[i]$ 代表 $0 \dots i$ 范围内最大的子数组和。

• 正确：$dp[i]$ 代表 必须以索引 $i$ 结尾 的连续子数组的最大和。

  • 为什么要这就定义？ 只有强制以 $i$ 结尾，我们才能根据 $dp[i-1]$ 保证子数组的连续性。

状态转移方程 (Transition)：

对于当前元素 nums[i]，我们面临两个选择：

1. 接力 (Join)：如果你前面的那个累积和 $dp[i-1]$ 是正能量（$>0$），那就把它加上，通过 nums[i] 延续这个子数组。

2. 另起炉灶 (Restart)：如果你前面的累积和 $dp[i-1]$ 是负资产（$<0$），加上它只会拖累自己，不如甩掉包袱，从 nums[i] 重新开始计算。

$dp[i] = \max(dp[i-1] + nums[i], \quad nums[i])$

或者更直观的理解：

$dp[i] = nums[i] + \max(dp[i-1], 0)$

---

2. 代码实现 (标准 DP 版)

这是 $O(N)$ 空间复杂度版本，逻辑非常清晰。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        // dp[i]: 以 nums[i] 结尾的最大连续子数组和
        vector<int> dp(n);
        
        // 初始化：第一个元素自成一派
        dp[0] = nums[0];
        int result = nums[0];

        for (int i = 1; i < n; i++) {
            // 决策：是"继承家业"还是"白手起家"？
            // 如果 dp[i-1] + nums[i] < nums[i]，说明 dp[i-1] 是负数(累赘)
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            
            // 记录历史最高峰值 (因为最大和不一定出现在数组末尾)
            result = max(result, dp[i]);
        }

        return result;
    }
};

---

3. 进阶优化：滚动数组 (Kadane 算法)

思考：我们在计算 $dp[i]$ 时，只需要用到 $dp[i-1]$。再之前的 $dp[i-2], dp[i-3] \dots$ 都不需要了。

优化：我们可以只用一个整型变量 pre 来代替整个 dp 数组，将空间复杂度从 $O(N)$ 降至 $O(1)$。这种做法就是著名的 Kadane 算法。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0;
        int maxAns = nums[0];
        
        for (const int& x : nums) {
            // pre 代表"以当前 x 结尾的最大和"
            // 这里的 max(pre + x, x) 等价于：如果 pre < 0，则置零重新开始
            pre = max(pre + x, x);
            
            // 更新全局最大值
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

---

4. 关键细节备忘

1. 全局最大值 vs 局部最大值：

   • $dp[i]$ 只是局部最优（必须包含 $i$）。

   • 题目要的是全局最优，所以必须用 result 变量在遍历过程中实时抓取 $dp[i]$ 的最大值。

2. 初始化陷阱：

   • result 必须初始化为 nums[0] 或 INT_MIN。

   • 切忌 初始化为 0。如果数组全是负数（如 [-2, -1]），初始化为 0 会导致错误返回 0，而正确答案应该是 -1。

3. 贪心视角的理解：

   • 这道题也可以看作是贪心算法：一旦当前的"连续和"变成了负数，它对后面的元素就没有任何增益了，直接抛弃归零。