[53] 最大子序和

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

示例：

输入：[-2,1,-3,4,-1,2,1,-5,4]\

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

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

动态规划解法

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

这道题得分两步考虑。想要求出在 0 -> n 点的最大子序列和，那么就要看 0 -> n-1 点的和是否为正数，如果为负数的话，那还不如就只取 n 点一个数作为子序列来得大了。

因此，我们可以得出 0-n 最大和的状态转移方程：Sn = MAX(nums[n], Sn-1 + nums[n])

第二步，我们需要选出整个数组中任意连续子序列的最大和。那么很简单，将从 0->1......0->n 中所有的最大和都记录下来，选择最大值即可。

由于本题不需要回溯子序列索引，因此不需要记录每一步的最大值。

function maxSubArray(nums: number[]): number {
  const len = nums.length;
  const dp = Array(len).fill(Number.MIN_SAFE_INTEGER);
  dp[0] = nums[0];
  let res = nums[0];

  // 状态转移方程：Sn = Math.max(nums[n], Sn-1 + nums[n])
  for (let i = 1; i < len; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    res = Math.max(res, dp[i]);
  }

  return res;
}

将代码稍微改动一下，就能输出最大子序列了。

function maxSubArray(nums: number[]): number {
  const len = nums.length;
  const dp = Array(len).fill(Number.MIN_SAFE_INTEGER);
  dp[0] = nums[0];

  let arr: number[] = [nums[0]];
  let resArr: number[] = [nums[0]];
  let res = nums[0];

  // 状态转移方程：Sn = Math.max(nums[n], Sn-1 + nums[n])
  for (let i = 1; i < len; i++) {
    if (dp[i - 1] < 0) {
      dp[i] = nums[i];
      arr = [nums[i]];
    } else {
      dp[i] = dp[i - 1] + nums[i];
      arr.push(nums[i]);
    }

    if (dp[i] > res) {
      // 此时更新子序列
      res = dp[i];
      resArr = [...arr];
    }
  }

  console.log(resArr);
  return res;
}

观察 dp 数组可知，dp[i] 仅与 dp[i-1] 相关，因此完全可以用一个变量替代 dp 数组，从而节省空间复杂度。

function maxSubArray(nums: number[]): number {
  let dp = nums[0];
  let res = nums[0];

  for (let i = 1; i < nums.length; i++) {
    dp = Math.max(nums[i], dp + nums[i]);
    res = Math.max(res, dp);
  }

  return res;
}

分治法

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

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);
}