力扣53.最大子数组和

张开发
• 2026/4/10 1:28:03 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣53.最大子数组和
给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例 1输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2输入nums [1]输出1示例 3输入nums [5,4,-1,7,8]输出23提示1 nums.length 105-104 nums[i] 104进阶如果你已经实现复杂度为O(n)的解法尝试使用更为精妙的分治法求解。思路1.前缀和result max((result,item-min_front_sum,item))实时更新前i位的子串中能得到的最大值result max已记录最大值前i位前缀和-前i位中的最小前缀和前i位前缀和2.动态规划class Solution: def maxSubArray(self, nums: List[int]) - int: #前缀和方法 # fron_sum [] # total 0 # for i in nums: # totali # fron_sum.append(total) # result None # min_front_sum None # flag 0 # for item in fron_sum: # #首次略过 # if not flag: # min_front_sum item # result item # flag1 # continue # result max((result,item-min_front_sum,item)) # min_front_sum min(min_front_sum,item) # return result #使用dp思想 截至当前位置能够获取的子串最大值实时更新max_val #情况1前一位的子串最大值0能够不减小/增长后续扩充的子串值 将前一位的子串最大值与该位置的值相加 得到截至当前位置能够获取的子串最大值 #情况2前一位的子串最大值0 抛弃前一位的子串最大值因为他会导致后续扩充的子串值减小 直接从当前位置开始计算新的子串最大值 #dp[i] (nums[i]dp[i-1] if dp[i-1]0 # elif dp[i-1]0: nums[i]) #(两种操作将当前元素加入前面的串中 or 重新开始计算) dp [nums[0]] result nums[0] for i in range(1,len(nums)): if dp[i-1]0: dp.append(nums[i]) else:dp.append(nums[i]dp[i-1]) result max(result,dp[-1]) return result

更多文章