题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解法一
暴力求解。思路简单，时间复杂度为 O(n*n)，会超时
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 暴力
if not nums: return 0
res = nums[0]
for l in range(len(nums)):
for j in range(l, len(nums)):
res = max(res, sum(nums[l:j+1]))
return res
解法二
动态规划。比较迭代过程中比较当前值与 上一次的dp值的和是否有超过当前值，否则只保留当前值填入当前dp即可。时间复杂度O(n), 空间复杂度 O(n)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 动态规划
dp = [nums[0]] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
# 如果当 num[i] > dp[i-1] + nums[i]，那么可以表示之前的可以舍弃重新开始
dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)
解法三
动态规划。时间复杂度O(n), 空间复杂度 O(1)。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 动态规划
res = cur = nums[0]
for i in range(1, len(nums)):
cur = max(nums[i], cur + nums[i])
res = max(res, cur)
return res
解法四
回溯 + 分治。分为左中右。看注释理解中间区域
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums: return 0
return self.__max_sub_array(nums, 0, len(nums) - 1)
def __max_sub_array(self, nums, left, right):
if left == right:
return nums[left]
mid = left + ((right - left) >> 1)
# 回溯 + 分治
return max(self.__max_sub_array(nums, left, mid),
self.__max_sub_array(nums, mid + 1, right),
self.__max_cross_array(nums, left, mid, right))
def __max_cross_array(self, nums, left, mid, right):
# 一定包含 nums[mid] 元素的最大连续子数组的和，
# 思路是看看左边"扩散到底"，得到一个最大数，右边"扩散到底"得到一个最大数
# 然后再加上中间数
left_sum_max, start_left, s1 = 0, mid - 1, 0
while start_left >= left:
s1 += nums[start_left]
left_sum_max = max(left_sum_max, s1)
start_left -= 1
right_sum_max, start_right, s2 = 0, mid + 1, 0
while start_right <= right:
s2 += nums[start_right]
right_sum_max = max(right_sum_max, s2)
start_right += 1
return left_sum_max + nums[mid] + right_sum_max
