算法练习6：求最大子序和（leetcode 53）

题目

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

暴力解法

max初始值设为第一个数，然后进行二层遍历，当前数与其它都累计相加sum，如果和sum＞max, 则更新max = sum

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

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  // 设置边界值
  if(nums.length <= 0) return null;
  if(nums.length === 1) return nums[0]
  // max初始值为第1个数
  let max = nums[0];
  for(let i = 0; i < nums.length; i++) {
    let sum = 0;
    for(let j = i; j < nums.length; j++) {
      sum += nums[j]
      if(sum > max) max = sum
    }
  }
  return max;
};

动态规则解法

对于每个数来说，它的最大子序列和有两种情况：

• 前面最大子序列如果大于0，那么它的最大子序列和就为：前面最大子序列之和 + 自身

• 如果前面最大子序列之和小于0，那么它的最大子序列就是它自身

  
  动态规则.png

如图中所示，为了方便，举个少一点数的例子[-2, 4,-3, 1, 7]

1. 对于第一个数-2来说，它前面没有序列，所以它的最大子序列和是它自身 -2，也就是dp[0] = nums[0] = -2

nums	-2
dp	-2

2. 对于第二个数4来说，它的子序列为[-2, 4]和[4]，它的子序列和分别为： -2 + 4 = 0 和 4，可以看出，如果前一个子序列和小于0，那么它的最大子序列就是它本身，即 dp[1] = max( dp[0] + nums[1], nums[1]) = nums[1] = 4

nums	-2	4
dp	-2	4

3. 对于第三个数-3来说，它的子序列为[-2, 4, -3]、[4, -3]、[-3]，它的子序列和分别为： -2 + 4 -3 = -1、4-3=1 和 -3，可以看出，自身是一定存在的，那么比的部分就是 -2 +4 、4和0的部分谁大，而-2 + 4 和 4的部分，恰好又是上一次dp[2]的结果，所以本质上是在比dp[2]和0的比较，即 dp[2] = max( dp[1] + nums[2], nums[2]) = dp[1] + nums[2] = 1

nums	-2	4	-3
dp	-2	4	1

4. 对于第四个数1来说，它的子序列为[-2, 4, -3、1]、[4, -3、1]、[-3、1]和[1]，它的子序列各分别为：0、2 、-2、1，可以看出，因为dp[2] > 0，即 dp[3] = max( dp[2] + nums[3], nums[3]) = dp[2] + nums[3]= 2

nums	-2	4	-3	1
dp	-2	4	1	2

5. 对于第五个数7来说，它的子序列为[-2, 4, -3、1、7]、[4, -3、1、7]、[-3、1、7]、[1、7]和[7]，它的子序列各分别为：7、9 、5、8、7，可以看出，因为dp[4] > 0，即 dp[4] = max( dp[3] + nums[4], nums[4]) = dp[3] + nums[3]= 2 + 7 = 9

nums	-2	4	-3	1	7
dp	-2	4	1	2	9

6. 当结果出来后，再遍历一次dp数组，找出最大值，就是所求的最大子序列和。

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray = function(nums) {
  for(let i = 1; i < nums.length; i++) {
    // dp可以利用nums本身数组内存作操作
    if(nums[i - 1] < 0) {
      nums[i] = nums[i]
    }else {
      nums[i] = nums[i - 1] + nums[i]
    }
  }
  // 遍历新得的dp数据，找出最大子序列和
  let max = nums[0];
  for(let i = 1; i < nums.length; i++) {
    if(nums[i] > max) {
      max = nums[i]
    }
  }
  return max;
};

再优化一下，直接在第一次遍历时，就记录最大dp值，就不需要再额外遍历一次了：

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray = function(nums) {
  let max = nums[0];
  for(let i = 1; i < nums.length; i++) {
    if(nums[i - 1] < 0) {
      nums[i] = nums[i]
    }else {
      nums[i] = nums[i - 1] + nums[i]
    }
    if(nums[i] > max) {
      max = nums[i]
    }
  }
  return max;
};

• 时间复杂度：O(n)
• 空间复杂度：新生成的数组dp是直接在原数组上改动的，未额外申请空间，只有一个max临时变量，所以为O(1)