[53] 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

这道题根据leetcode给的tag提示，我们有两种解题思路。

动态规划解法

一种是利用动态规划的思想

状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])

原始动态规划解法，由于本题不需要回溯子序列索引，因此不需要记录每一步的最大值

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

观察dp数组可知，dp[i]仅与dp[i-1]相关，因此完全可以用一个变量替代dp数组，从而节省空间复杂度。（下面的解顺便求了最大子序列）

var maxSubArray = function(nums) {
  let dp = nums[0];
  let res = nums[0];
  let tempArr = [nums[0]];
  let resArr = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < dp + nums[i]) {
      dp = nums[i] + dp;
      tempArr.push(nums[i]);
    } else {
      dp = nums[i];
      tempArr = [nums[i]];
    }
    if (res < dp) {
      res = dp;
      resArr = [...tempArr];
    }
  }
  console.log(resArr);
  return res;
};

最后的解如下：

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

分治法

最大子序列和的位置有以下三种情况：

1. 考虑中间元素nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。
2. 不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
3. 不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和 分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。

var maxSubArray = function(nums) {
  return SubHelper(nums, 0, nums.length - 1);
};

function SubHelper(nums, l, r) {
  if (l === r) return nums[l];
  let sum = 0;
  let leftMax = Number.MIN_SAFE_INTEGER;
  let rightMax = Number.MIN_SAFE_INTEGER;
  const mid = l + ((r - l) >> 1);
  const subLeft = SubHelper(nums, l, mid);
  const subRight = SubHelper(nums, mid + 1, r);
  for (let i = mid; i >= l; i--) {
    sum += nums[i];
    if (sum > leftMax) leftMax = sum;
  }
  sum = 0;
  for (let i = mid + 1; i <= r; i++) {
    sum += nums[i];
    if (sum > rightMax) rightMax = sum;
  }
  return Math.max(leftMax + rightMax, subLeft, subRight);
}