leetcode53_最大子序和
163 浏览量
2020-12-22
06:19:37
上传
评论
收藏 41KB PDF 举报
leetcode53_最大子序和最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
暴力法，
我们通过i和j记录子序列的左右边界，然后遍历所有的边界，寻找区间[i:j]和最大是多少即可。
时间复杂度O(n2) 空间复杂度 O(1)
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsub = nums[0] for i in range(0, len(nums) - 1):
mysum = 0
for j in range(i, len(nums) - 1):
mysum += nums[j] if mysum > maxsub:
maxsub = mysum
return maxsub
我们这里只要求子序列的最大和，不要求得到子序列本身，其实就暗示了动态规划、分治
分治，我们把数组nums以中间位置m分为左（left)右(right)两部分， left = nums[0]…nums[m – 1] 和 right = nums[m + 1]…
nums[n-1]，最大子序列有以下三种情况：
跨越左右两部分，这里从中间元素开始，往左求出最大，往右求出最大, 保持连续性。
不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和
时间复杂度： O(nlogn)
空间复杂度： O(logn) – 因为二分法，调用栈的深度最多是logn。
import sys
class Solution:
def helper(self, nums, l, r):
if l > r:
return -sys.maxsize
mid = (l + r) // 2
# 假如最大子序列在左半部分，这种情况的最大和
left = self.helper(nums, l, mid - 1)
# 假如最大子序列在右半部分，这种情况的最大和
right = self.helper(nums, mid + 1, r)
# 假如最大子序列横跨左右两半，这种情况的最大和：
# 左边部分连续序列能有的最大和+右边部分连续序列能给出的最大和+中间值
left_suffix_max_sum = right_prefix_max_sum = 0
mysum1 = 0
for i in reversed(range(l, mid)):
mysum1 += nums[i] left_suffix_max_sum = max(mysum1, left_suffix_max_sum)
mysum2 = 0
for i in range(mid + 1, r + 1):
mysum2 += nums[i] right_prefix_max_sum = max(mysum2, right_prefix_max_sum)
cross_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid] return max(left, right, cross_sum)
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums) - 1)
动态规划，动态规划的难点在于找到状态转移方程，
dp[i] – 表示到当前位置 i 的最大子序列和
状态转移方程为： dp[i] = max(dp[i – 1] + nums[i], nums[i])
初始化：dp[0] = nums[0]
从状态转移方程中，我们只关注前一个状态的值，所以不需要开一个数组记录位置所有子序列和，只需要两个变量，
currMaxSum – 当前位置 i 的最大和
maxSum – 全局最大和:
currMaxSum = max(currMaxSum + nums[i], nums[i])
maxSum = max(currMaxSum, maxSum)
评论0
最新资源