题目描述

[EN | CN]

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

示例:

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

进阶:

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

解法 1:直接法

题目说了要 $O(n)$ 复杂度,也就是说不能暴力双循环,只能若干次扫描。

对于前 $i - 1$ 个数,如果其最大值为 $M_{i - 1}$,那么当我们扫描到第 $i$ 个元素 $n_i$时,可以有两种选择:

  • 保留前面选中的数组,加上 $n_i$ 这个数,此时 $M_i = M_{i - 1} + n_i$;
  • 丢弃前面选中的数组,从 $n_i$ 重新开始,此时 $M_i = n_i$。

所以实际上我们只需要比较这两种选择的大小,取 max 即可得到我们扫描到第 $i$ 个元素时的最大值。那么整个数组只需要扫描一遍,保留一个本地的最大值、全局的最大值,最后返回全局最大值。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,只保存一个最大值。

实现与结果如下:

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        local_max = nums[0]
        global_max = nums[0]
        for n in nums[1:]:
            local_max = max(local_max + n, n)
            global_max = max(global_max, local_max)
        return global_max
  • 执行用时:2528 ms,在所有 Python3 提交中击败了 15.41% 的用户。
  • 内存消耗:17.8 MB,在所有 Python3 提交中击败了 6.67% 的用户。

解法 2:Inplace 直接法

如果题目允许直接 inplace 修改数组 nums 的话,可以将解法 1 写得更加简洁,时间、空间复杂度保持不变。

实现与结果如下:

1
2
3
4
5
6
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]
        return max(nums)
  • 执行用时:48 ms,在所有 Python3 提交中击败了 80.58% 的用户。
  • 内存消耗:14.5 MB,在所有 Python3 提交中击败了 6.35% 的用户。

解法 3:分治法

分治法挺麻烦的,不知道为什么题目会推荐分治法。

如果要使用分治法的话,就每次将数组二等分,分别计算左子数组、右子数组的结果,然后合并。合并的时候需要考虑 3 种情况:

  • 左子数组结果最大;
  • 左子数组结果最大;
  • 左子数组的右边部分与右子数组的左边部分加起来的结果最大。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n\log n)$,每次都要二等分来解决问题所以有个 $\log n$,合并的时候需要 $\frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \cdots$ 次比较与合并所以有个 $n$;
  • 空间复杂度为 $O(\log n)$,递归是需要付出代价的(栈深)。

实现与结果略。