最大子序和-53

[sl1673495]

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释:  连续子数组  [4,-1,2,1] 的和最大，为  6。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题评论区普遍反应不应该是 easy 难度，实际上确实是比较有难度的。这题有 DP 来做的话，状态转移方程和打劫问题类似。找两种情况中的最大值：

1. 只选择当前的数字。
2. 选择当前的数字 + 下一个数字开始求得的最大值。

如果选项 1 比选项 2 要大，那么说明后面的都抛弃掉，从当前数字开始作为子数组的起点。

比如 [2, -2, 1] 来说，先从最右边开始，dp[2]的最大值是 1。

然后求 dp[1]，选出两种情况，分别是只选择 -2， 和选择 -2 + 1 = -1，明显是后者更大，所以 dp[1]的值更新为 -1。此时可以想象一下，dp[1] 记录的值其实就是 [-2, 1] 这个连续子数组的和。

然后再往左到了 dp[0]，分别是只选择 2，和选择 2 + -1 = 1，当然是只选择 2 更大，此时右边的子数组中断，dp[0] 上记录的其实是子数组 [2]

最后需要返回 dp 数组中的最大值，因为子数组的起点是不确定的。这样就找到了 dp[0] 上保留的 [2] 这个最大子数组。

这不是一个简单的自底向上求解，然后返回最顶部的值的 DP 问题。

题解

/**
 * @param {number[]} nums
 * @return {number}
 */
let maxSubArray = function(nums) {
  let n = nums.length;
  let dp = [];

  dp[n - 1] = nums[n - 1];

  for (let i = n - 2; i >= 0; i--) {
    let pickSelf = nums[i];
    let pickWithNext = pickSelf + dp[i + 1];
    dp[i] = Math.max(pickSelf, pickWithNext);
  }

  return Math.max(...dp);
};