- 标签:数组、分治、动态规划
- 难度:中等
描述:给定一个整数数组
要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
说明:
- 子数组:指的是数组中的一个连续部分。
-
$1 \le nums.length \le 10^5$ 。 -
$-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
按照连续子数组的结束位置进行阶段划分。
定义状态
状态
- 如果
$dp[i - 1] < 0$ ,则「第$i - 1$ 个数结尾的连续子数组的最大和」+「第$i$ 个数的值」<「第$i$ 个数的值」,即:$dp[i - 1] + nums[i] < nums[i]$。所以,此时$dp[i]$ 应取「第$i$ 个数的值」,即$dp[i] = nums[i]$ 。 - 如果
$dp[i - 1] \ge 0$ ,则「第$i - 1$ 个数结尾的连续子数组的最大和」 +「第$i$ 个数的值」 >= 第$i$ 个数的值,即:$dp[i - 1] + nums[i] \ge nums[i]$。所以,此时$dp[i]$ 应取「第$i - 1$ 个数结尾的连续子数组的最大和」+「 第$i$ 个数的值」,即$dp[i] = dp[i - 1] + nums[i]$ 。
归纳一下,状态转移方程为:
$dp[i] = \begin{cases} nums[i], & dp[i - 1] < 0 \cr dp[i - 1] + nums[i] & dp[i - 1] \ge 0 \end{cases}$
- 第
$0$ 个数结尾的连续子数组的最大和为$nums[0]$ ,即$dp[0] = nums[0]$ 。
根据状态定义,$dp[i]$ 为:以第
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)
-
时间复杂度:$O(n)$,其中
$n$ 为数组$nums$ 的元素个数。 - 空间复杂度:$O(n)$。
因为
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
-
时间复杂度:$O(n)$,其中
$n$ 为数组$nums$ 的元素个数。 - 空间复杂度:$O(1)$。
我们将数组
- 具有最大和的连续子数组在左子数组中。
- 具有最大和的连续子数组在右子数组中。
- 具有最大和的连续子数组跨过中心位置,一部分在左子数组中,另一部分在右子树组中。
那么我们要求出具有最大和的连续子数组的最大和,则分别对上面
- 将数组
$nums$ 根据中心位置递归分为左右两个子数组,直到所有子数组长度为$1$ 。 - 长度为
$1$ 的子数组最大和肯定是数组中唯一的数,将其返回即可。 - 求出左子数组的最大和
$leftMax$ 。 - 求出右子树组的最大和
$rightMax$ 。 - 求出跨过中心位置,一部分在左子数组中,另一部分在右子树组的子数组最大和
$leftTotal + rightTotal$ 。 - 求出
$3$ 、$4$、$5$ 中的最大值,即为当前数组的最大和,将其返回即可。
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)
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(\log n)$。