53. 最大子序和

题目

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

例

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

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

进阶:

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

题解

贪心

之前的数组之和为负数的时候就重新计算，否则加上当前值

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let ans = -Infinity;
  let pre = 0;
  for (let n of nums) {
    if (pre >= 0) pre += n;
    else pre = n;
    ans = Math.max(pre, ans);
  }
  return ans;
};

动态规划

a_i 代表第 i 个数

f(i) 代表以第 i 个数结尾的连续子数组的最大和

题目所求即是：

max{f{i}} 0<=i<=n-1

而 f(i) 依赖于 f(i-1) 和 a_i ：

f(i) = max{f(i-1)+a_i,a_i}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let pre = 0;
  max = nums[0]; // 边界
  for (let num of nums) {
    // 状态转移方程
    pre = Math.max(num, pre + num);
    max = Math.max(pre, max);
  }
  return max;
};

时间复杂度：O(n) 空间复杂度：O(1)

分治法

我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l, r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l, r]，我们取 m = (l+r)/2，对区间 [l, m] 和 [m + 1, r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l, m] 区间的信息和 [m + 1, r] 区间的信息合并成区间 [l, r] 的信息。最关键的两个问题是：

• 要维护区间的哪些信息呢？
• 如何合并这些信息呢？

对于一个区间 [l, r]，我们可以维护四个量：

• lSum 表示 [l, r] 内以 l 为左端点的最大子段和

• rSum 表示 [l, r] 内以 r 为右端点的最大子段和

• mSum 表示 [l, r] 内的最大子段和

• iSum 表示 [l, r] 的区间和

• 最好维护的是 iSum，区间 [l, r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。

• lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。

• rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。

当计算好上面的三个量之后，就很好计算 mSum 了。我们可以考虑 [l, r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l, r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。 这样问题就得到了解决。

function Status(l, r, m, i) {
  this.lSum = l;
  this.rSum = r;
  this.mSum = m;
  this.iSum = i;
}

const pushUp = (l, r) => {
  const iSum = l.iSum + r.iSum;
  const lSum = Math.max(l.lSum, l.iSum + r.lSum);
  const rSum = Math.max(r.rSum, r.iSum + l.rSum);
  const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
  return new Status(lSum, rSum, mSum, iSum);
};

const getInfo = (a, l, r) => {
  if (l === r) return new Status(a[l], a[l], a[l], a[l]);
  const m = (l + r) >> 1;
  const lSub = getInfo(a, l, m);
  const rSub = getInfo(a, m + 1, r);
  return pushUp(lSub, rSub);
};

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