leetcode53_最大子序和_leetcode53资源-CSDN下载

84 浏览量 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)

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

内容反馈

weixin_38500222

粉丝: 5

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip