【剑指Offer】面试题42：连续子数组的最大和

发表于 | 分类于 | 阅读次数:

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

例如，输入的数组为 {1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和 18。

思路 1：穷举

最直接的思路就是：穷举数组的所有子数组的情况，然后计算它们的和，找出最大的值。子数组的数量为 $\frac{n(n - 1)}{2}$，因此时间复杂度为 $O(n^2)$，这个时间复杂度是不能让人接受的，我们还得想想其他办法。

思路 2：举例分析数组的规律

当我们没有什么思路时，我们可以举例来分析一下数组的规律。我们尝试从头到尾的逐个累加数组中的数字。初始化和为 0。

  1. 累加第一个数字 1。和为 1
  2. 累加第二个数字 -2。和为 -1，小于 0
  3. 累加第三个数字 3。和为 2。这个和比第三个数字的值还小，我们舍弃之前的子数组，从当前数字开始重新累加。这时，和为3

从以上分析中，我们可以发现，一旦累加和小于 0 之后，以这个数为结尾的子数组对于求解和最大的子数组就没什么用了，这是应该舍弃，然后从将和归零，重新累加寻找和最大的子数组。

  1. 累加第四个数字 10。和为 13
  2. 累加第五个数字 -4。和为 9
  3. 累加第六个数字 7。和为 16
  4. 累加第七个数字 2。和为 18
  5. 累加第八个数字 -5。和为 13

每次累加一个数字其实就相当于在子数组中增加一个数字，计算和也就是计算这个子数组的和。从以上的分析中，我们可以发现，当累加到第七个数字时，和最大，此时的子数组为 {3, 10, -4, 7, 2}，该子数组的和 18 就是我们要找的最大和。

因此，我们可以将思路总结一下：从头到尾的累加数组中的数字，当累加和小于 0 时，就舍弃此时的累加并重置和为当前数字；使用一个临时变量记录累加过程中计算的和的最大值。

该算法只需要从头到尾的遍历一遍数组即可，因此时间复杂度是 O(n)。

思路 3：动态规划

一旦涉及到求最值的问题，一般都可以用动态规划来解。这道题希望求解最大值，并且求解的是数组的子数组的相关问题，可能会有重叠的子问题，可以使用动态规划来解。

我们使用 f(i) 来表示以数组中第 i 个数字结尾的子数组的最大和，因此我们需要求解数组中以每个数字结尾的子数组的最大和的最大值，也就是 $max \, f(i), \, 0 \leq i \lt n$。状态转移方程满足：

$$
f(i) =
\begin{cases}
pData[i], & i=0 \lor f(i-1) \leq 0\\
f(i-1) + pData[i], & i \neq 0 \land f(i-1)>0
\end{cases}
$$

这个公式表示：如果第 i-1 个数字结尾的子数组的和小于 0，那么第 i 个数字结尾的子数组就舍弃之前的数字，只包含第 i 个数字，此时的和为第 i 个数字本身；否则，“第 i 个数字结尾的子数组的和” = “第 i-1 个数字结尾的子数组的和” + “第 i 个数字”。

实际上，你仔细想想，思路 3 和思路 2 在本质上是相同的，只是表达方式不一样。这个思路的时间复杂度同样是 O(n)。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        // 特殊输入的检查
        if (array == null || array.length == 0)
            return 0;
        if (array.length == 1)
            return array[0];

        // 动态规划
        int max = array[0];
        int lastSum = array[0];
        for (int i = 1; i < array.length; i++) {
            lastSum = Math.max(lastSum + array[i], array[i]);
            if (max < lastSum)
                max = lastSum;
        }

        return max;
    }
}