53.最大子数组和

题目

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入： nums = [1]
输出： 1

示例 3：

输入： nums = [5,4,-1,7,8]
输出： 23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

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

思路

实话说，我费了老大的功夫最后也没能通过所有的用例，所以在此记录一下。

错误解法

一开始我想到的是，通过两端删减元素的方法，一步步算出中间遇到的所有可能产生更大和的数组，从而完成题解。讲道理这个思路理论上可行，但是实际执行起来有很多问题。

首先，当数组的首尾两端存在一个更小的负值的时候，删除它会让数组的和变大。①

其次，控制首尾删除一个和为负数的子数组，也可以让数组的和变大。…… 吗？②

举个栗子🌰：

1
nums = [2, 0, -1, 0, -2, -3, 1, 2]

可以看到，数组左边的最短负数和数组为 [2,0,-1,0,-2]，数组右边的最短负数和数组为 [-2,-3,1,2]，按照 ②，应该删除右边的数组。但是这个数组的最大子数组和恰好是右边删除的这个数组的子数组 [1,2]的和，也就是说，在删除负数和数组的时候，会有可能，因为一个巨大的负数，而删除了答案对应的子数组。

现在回过头来看 ② 的描述，乍一看似乎没有问题，但是对于这道题来说，经过 ② 处理的子数组确实和比处理前的数组和大，但是删除的子数组存在一个更大的子数组和。

事实上，即使是 ①，对于这道题也有待商榷，因为删除的元素可能比剩下的数组和还要大。

综上，这一解法不可取。

动态规划解

从上一个错误的解法中吸取教训，这次首先尝试遍历所有子数组（子序列）方法，这总可以得到结果。

然后从一个 题解 得到了这样一句话:

通常我们遍历子串或者子序列有三种遍历方式

  • 以某个节点为开头的所有子序列: 如 [a]，[a, b]，[ a, b, c] … 再从以 b 为开头的子序列开始遍历 [b] [b, c]。
  • 根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的 等等。
  • 以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。

这里的第三种方式存在递推关系，适合动态规划：

在此贴一下 hello 算法 对于 动态规划的定义

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

如文中 14.1.3 小节提到的，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

对于这道题，假设对于结尾为 a 的数组，其最大和的子数组，只与

  1. 之前的数组的连续子数组最大和 sum 与结尾元素的和
  2. 结尾元素

这两个值相关，取决于谁更大。即，Math.max(sum + a, a)

因此可以写出这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var maxSubArray = function (nums) {
  const preArr = []; // 以每一个元素结尾的有连续最大和的子数组的数组
  let max = nums[0];
  nums.forEach((item) => {
    let sum = nums[0];
    if (preArr.length) {
      sum = preArr[preArr.length - 1].reduce((p, c) => ((p += c), p), 0);
      if (sum + item >= item) {
        preArr.push([...preArr[preArr.length - 1], item]);
      } else {
        preArr.push([item]);
      }
    } else {
      preArr.push([item]);
    }
    max = Math.max(sum, max);
    console.log(max);
  });
  console.log(preArr);
  return max;
};

这里故意打印出 max 的每一次变更值和 preArr 本身，可以更清晰的看到运行时获取到的连续子数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// max 增长序列
-2
-2
1
1
4
4
5
6
6

// preArr
[
  [ -2 ], // 以 -2 结尾的有最大和的连续子数组
  [ 1 ], // 以 1 结尾的有最大和的连续子数组
  [ 1, -3 ], // ...
  [ 4 ],
  [ 4, -1 ],
  [ 4, -1, 2 ],
  [ 4, -1, 2, 1 ],
  [ 4, -1, 2, 1, -5 ],
  [ 4, -1, 2, 1, -5, 4 ]
]

上述代码求出了以任意元素结尾的拥有最大和的连续子数组，按题意，找出它们中的和最大值即可。可以看到，[4,-1,2,1] 即为最终答案对应的数组。

考虑到过程并不重要，只有每一步的最大值最重要，所以 preArr 可以简化为一个 pre 值，表示前一次循环后的连续子数组的最大和，于是可以精简为以下的代码：

解

动态规划解

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let pre = 0;
  let max = nums[0];
  nums.forEach((item) => {
    pre = Math.max(pre + item, item);
    max = Math.max(pre, max);
  });
  return max;
};

看来我还得好好重新学习一下动态规划，目前已经把动态规划搞混了，甚至写这一篇题解也费了好大劲才考虑清楚。至于分治解，在这道题里不是最优解，故略去。