53.最大子数组和

LeetCode 原题链接 题目

实现思路

  • 定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最大子数组和。
  • 初始化 dp[0] 为 nums[0]。
  • 从 i = 1 开始遍历数组，对于每个位置 i，有两种选择：
    • 以 nums[i] 自身作为一个新的子数组的开始，即 nums[i]。
    • 将 nums[i] 加入到以 nums[i - 1] 结尾的最大子数组中，即 dp[i - 1] + nums[i]。
  • 因此，状态转移方程为：dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])。
  • 在计算 dp 数组的同时，维护一个变量 maxSum 来记录当前的最大子数组和，最终返回 maxSum。

代码实现

var maxSubArray = function (nums) {
  const dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }
  return Math.max(...dp);
};

关键点

为什么比较 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] 结尾的最大子数组，要么从自己开始，要么接在前面的最大子数组后面，没有第三种情况。