跳至主要內容

0053. 最大子数组和

ITCharge大约 4 分钟

0053. 最大子数组和open in new window

  • 标签:数组、分治、动态规划
  • 难度:中等

题目链接

题目大意

描述:给定一个整数数组 numsnums

要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

说明

  • 子数组:指的是数组中的一个连续部分。
  • 1nums.length1051 \le nums.length \le 10^5
  • 104nums[i]104-10^4 \le nums[i] \le 10^4

示例

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

解题思路

思路 1:动态规划

1. 划分阶段

按照连续子数组的结束位置进行阶段划分。

2. 定义状态

定义状态 dp[i]dp[i] 为:以第 ii 个数结尾的连续子数组的最大和。

3. 状态转移方程

状态 dp[i]dp[i] 为:以第 ii 个数结尾的连续子数组的最大和。则我们可以从「第 i1i - 1 个数结尾的连续子数组的最大和」,以及「第 ii 个数的值」来讨论 dp[i]dp[i]

  • 如果 dp[i1]<0dp[i - 1] < 0,则「第 i1i - 1 个数结尾的连续子数组的最大和」+「第 ii 个数的值」<「第 ii 个数的值」,即:dp[i1]+nums[i]<nums[i]dp[i - 1] + nums[i] < nums[i]。所以,此时 dp[i]dp[i] 应取「第 ii 个数的值」,即 dp[i]=nums[i]dp[i] = nums[i]
  • 如果 dp[i1]0dp[i - 1] \ge 0,则「第 i1i - 1 个数结尾的连续子数组的最大和」 +「第 ii 个数的值」 >= 第 ii 个数的值,即:dp[i1]+nums[i]nums[i]dp[i - 1] + nums[i] \ge nums[i]。所以,此时 dp[i]dp[i] 应取「第 i1i - 1 个数结尾的连续子数组的最大和」+「 第 ii 个数的值」,即 dp[i]=dp[i1]+nums[i]dp[i] = dp[i - 1] + nums[i]

归纳一下,状态转移方程为:

dp[i]={nums[i],dp[i1]<0dp[i1]+nums[i]dp[i1]0dp[i] = \begin{cases} nums[i], & dp[i - 1] < 0 \cr dp[i - 1] + nums[i] & dp[i - 1] \ge 0 \end{cases}

4. 初始条件
  • 00 个数结尾的连续子数组的最大和为 nums[0]nums[0],即 dp[0]=nums[0]dp[0] = nums[0]
5. 最终结果

根据状态定义,dp[i]dp[i] 为:以第 ii 个数结尾的连续子数组的最大和。则最终结果应为所有 dp[i]dp[i] 的最大值,即 max(dp)max(dp)

思路 1:代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] < 0:
                dp[i] = nums[i]
            else:
                dp[i] = dp[i - 1] + nums[i]
        return max(dp)

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 numsnums 的元素个数。
  • 空间复杂度O(n)O(n)

思路 2:动态规划 + 滚动优化

因为 dp[i]dp[i] 只和 dp[i1]dp[i - 1] 和当前元素 nums[i]nums[i] 相关,我们也可以使用一个变量 subMaxsubMax 来表示以第 ii 个数结尾的连续子数组的最大和。然后使用 ansMaxansMax 来保存全局中最大值。

思路 2:代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        subMax = nums[0]
        ansMax = nums[0]

        for i in range(1, size):
            if subMax < 0:
                subMax = nums[i]
            else:
                subMax += nums[i]
            ansMax = max(ansMax, subMax)
        return ansMax

思路 2:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 numsnums 的元素个数。
  • 空间复杂度O(1)O(1)

思路 3:分治算法

我们将数组 numsnums 根据中心位置分为左右两个子数组。则具有最大和的连续子数组可能存在以下 33 种情况:

  1. 具有最大和的连续子数组在左子数组中。
  2. 具有最大和的连续子数组在右子数组中。
  3. 具有最大和的连续子数组跨过中心位置,一部分在左子数组中,另一部分在右子树组中。

那么我们要求出具有最大和的连续子数组的最大和,则分别对上面 33 种情况求解即可。具体步骤如下:

  1. 将数组 numsnums 根据中心位置递归分为左右两个子数组,直到所有子数组长度为 11
  2. 长度为 11 的子数组最大和肯定是数组中唯一的数,将其返回即可。
  3. 求出左子数组的最大和 leftMaxleftMax
  4. 求出右子树组的最大和 rightMaxrightMax
  5. 求出跨过中心位置,一部分在左子数组中,另一部分在右子树组的子数组最大和 leftTotal+rightTotalleftTotal + rightTotal
  6. 求出 334455 中的最大值,即为当前数组的最大和,将其返回即可。

思路 3:代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def max_sub_array(low, high):
            if low == high:
                return nums[low]

            mid = low + (high - low) // 2
            leftMax = max_sub_array(low, mid)
            rightMax = max_sub_array(mid + 1, high)

            total = 0
            leftTotal = -inf
            for i in range(mid, low - 1, -1):
                total += nums[i]
                leftTotal = max(leftTotal, total)
            
            total = 0
            rightTotal = -inf
            for i in range(mid + 1, high + 1):
                total += nums[i]
                rightTotal = max(rightTotal, total)
            
            return max(leftMax, rightMax, leftTotal + rightTotal)
        
        return max_sub_array(0, len(nums) - 1)

思路 3:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(logn)O(\log n)