#53. 最大子数组和

LeetCode 原题链接

#题目要解决什么

给定一个整数数组 nums，找出一个和最大的非空连续子数组，并返回它的元素总和。

这里有两个重要限制：

• 子数组必须连续，不能跳过中间元素。
• 子数组不能为空，即使所有元素都是负数，也必须选择至少一个元素。

例如：

nums = [-2,1,-3,4,-1,2,1,-5,4]

和最大的连续子数组是：

[4,-1,2,1]

它的和为 6。

#为什么使用动态规划

遍历到 nums[i] 时，需要判断：

前面的连续子数组是否值得保留？

如果前面的子数组和是正数，把 nums[i] 接在它后面会得到更大的和；如果前面的子数组和是负数，继续携带它只会拖累当前结果，不如从 nums[i] 重新开始。

这说明当前位置的最优选择依赖于前一个位置的最优结果，符合动态规划的特征。

#DP 状态定义

定义：

dp[i] = 必须以 nums[i] 结尾的连续子数组的最大和

“必须以 nums[i] 结尾”非常重要。dp[i] 不是前 i 个元素中的全局最大子数组和，而是一个带有结尾限制的局部最优解。

例如：

nums = [4, -1, 2, 1, -5]

其中：

dp[3] = 6

表示以 nums[3] = 1 结尾的最大子数组是 [4,-1,2,1]。

而：

dp[4] = 1

表示必须以 nums[4] = -5 结尾时，最大和只能是：

4 + (-1) + 2 + 1 + (-5) = 1

虽然 dp[4] 比 dp[3] 小，但此前出现过的答案 6 仍然是整个数组的最大子数组和。因此最终答案是所有 dp[i] 中的最大值：

max(dp[0], dp[1], ..., dp[n - 1])

#状态转移

为了让子数组以 nums[i] 结尾，只有两种可能：

#选择一：从当前位置重新开始

不保留前面的子数组，只选择当前元素：

[nums[i]]

此时子数组和为：

nums[i]

#选择二：接在前一个最优子数组后面

保留以 nums[i - 1] 结尾的最大子数组，再把 nums[i] 接到末尾：

dp[i - 1] + nums[i]

两种选择取较大值：

dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);

也可以把 nums[i] 提取出来：

dp[i] = nums[i] + Math.max(0, dp[i - 1]);

这两个公式完全等价，第二个公式更直观地表达了：

前面的最大和大于 0  → 带上它
前面的最大和小于 0  → 丢掉它，从当前位置重新开始

#初始化

第一个元素前面没有其他元素，而且题目要求子数组非空，因此：

dp[0] = nums[0];

不能初始化为 0。如果输入是：

[-3, -2, -5]

正确答案应该是 -2，而不是空数组的和 0。

#代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  /*
   * dp[i] 表示必须以 nums[i] 结尾的连续子数组的最大和。
   * dp 中的每个位置记录一个局部最优解。
   */
  const dp = new Array(nums.length).fill(0);

  // 第一个位置只能选择 nums[0] 本身。
  dp[0] = nums[0];

  // 从第二个元素开始，逐个计算以当前位置结尾的最大子数组和。
  for (let i = 1; i < nums.length; i++) {
    /*
     * 两种选择：
     * 1. 从 nums[i] 重新开始，子数组和为 nums[i]；
     * 2. 接在前一个最优子数组后面，和为 dp[i - 1] + nums[i]。
     */
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }

  /*
   * dp[i] 只表示“以 i 结尾”的局部答案。
   * 最大子数组可能在任意位置结束，所以要取整个 dp 数组的最大值。
   */
  return Math.max(...dp);
};

#示例推演

以：

nums = [-2,1,-3,4,-1,2,1,-5,4]

为例：

最终：

dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]

其中最大值为 6，所以答案是 6。

注意最后的 dp[8] 是 5，不是最终答案 6。这再次说明：

dp[i] 只负责以 i 结尾的局部最优解
最终答案需要取所有 dp[i] 的最大值

#为什么转移不会遗漏答案

#为什么比较 nums[i] 和 dp[i - 1] + nums[i]？

因为 dp[i] 的定义是：必须以 nums[i] 结尾的最大子数组和。

所以遍历到 nums[i] 时，只有两种选择：

• 从 nums[i] 重新开始一个子数组，此时子数组和是 nums[i]。
• 把 nums[i] 接到前面的最大子数组后面，此时子数组和是 dp[i - 1] + nums[i]。

因此需要比较：

Math.max(nums[i], dp[i - 1] + nums[i]);

如果 dp[i - 1] 是负数，继续加上它会拖累当前结果，就应该从 nums[i] 重新开始；如果 dp[i - 1] 是正数，接上前面的子数组会让结果更大。

一句话总结：对于以 nums[i] 结尾的最大子数组，要么从自己开始，要么接在前面的最大子数组后面，没有第三种情况。

这里之所以可以直接使用 dp[i - 1]，是因为任何以 nums[i] 结尾且长度大于 1 的连续子数组，删除最后一个元素后，都必然是一个以 nums[i - 1] 结尾的连续子数组。

既然要选择这一类子数组中和最大的那个，前半部分自然应该采用 dp[i - 1]，而不需要枚举更早的起点。

#空间优化

计算 dp[i] 时只依赖 dp[i - 1]，不需要保留完整的 dp 数组。因此可以使用：

• currentSum：当前必须以 nums[i] 结尾的最大子数组和。
• maxSum：到目前为止出现过的全局最大子数组和。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  // 两个变量都从 nums[0] 开始，保证全负数输入也能得到正确答案。
  let currentSum = nums[0];
  let maxSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    /*
     * currentSum 对应原来的 dp[i]：
     * 要么从 nums[i] 重新开始，要么接在前一个连续子数组后面。
     */
    currentSum = Math.max(nums[i], currentSum + nums[i]);

    // 当前子数组可能刷新整个遍历过程中的最大值。
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
};

这就是 Kadane 算法。它和 DP 数组写法使用相同的状态转移，只是把空间从 O(n) 优化到了 O(1)。

#全负数为什么也能正确处理

考虑：

nums = [-3, -2, -5]

计算过程为：

dp[0] = -3
dp[1] = max(-2, -3 + -2) = -2
dp[2] = max(-5, -2 + -5) = -5

所以：

dp = [-3, -2, -5]

最大值为 -2。

算法不会错误地返回 0，因为状态始终表示非空子数组，并且初始化使用的是 nums[0]。

#复杂度分析

#DP 数组写法

• 时间复杂度：O(n)，只遍历数组一次。
• 空间复杂度：O(n)，需要保存完整的 dp 数组。

#空间优化写法

• 时间复杂度：O(n)。
• 空间复杂度：O(1)，只使用 currentSum 和 maxSum。

#常见错误

• 把 dp[i] 错误理解成前 i 个元素的最大子数组和。
• 只返回最后一个状态 dp[nums.length - 1]，而没有取所有状态的最大值。
• 把初始最大值设为 0，导致全负数数组返回错误结果。
• 把题目当成子序列问题，跳过中间的负数元素，忽略了“连续”条件。
• 看到当前元素是负数就立即丢弃它；负数虽然会降低和，但可能连接前后两个正数区间。

#一句话总结

currentSum 决定“要不要带上前面的连续子数组”，
maxSum 负责记录“历史上出现过的最大答案”。