宁波市鄞州区建设局网站,建设卡开通网银网站,最好的个人网站建设,简历生成网站LeetCode 热题 100 | 53. 最大子数组和
大家好#xff0c;今天我们来解决一道经典的算法题——最大子数组和。这道题在 LeetCode 上被标记为中等难度#xff0c;要求我们找出一个具有最大和的连续子数组#xff0c;并返回其最大和。下面我将详细讲解解题思路#xff0c;并…LeetCode 热题 100 | 53. 最大子数组和
大家好今天我们来解决一道经典的算法题——最大子数组和。这道题在 LeetCode 上被标记为中等难度要求我们找出一个具有最大和的连续子数组并返回其最大和。下面我将详细讲解解题思路并附上 Python 代码实现。 题目描述
给定一个整数数组 nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
示例
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6。解题思路
这道题的核心是找到一个连续子数组使得其和最大。我们可以使用 动态规划 或 分治法 来解决这个问题。
核心思想 动态规划 定义 dp[i] 表示以 nums[i] 结尾的子数组的最大和。状态转移方程 dp[i] max(dp[i-1] nums[i], nums[i])最终结果是 dp 数组中的最大值。 分治法 将数组分成左右两部分分别求解左右部分的最大子数组和。求解跨越中间的最大子数组和。返回左部分、右部分和跨越中间的最大值。 代码实现
方法 1动态规划
def maxSubArray(nums)::type nums: List[int]:rtype: intn len(nums)dp [0] * ndp[0] nums[0] # 初始化 dp[0]max_sum dp[0] # 初始化最大和for i in range(1, n):dp[i] max(dp[i-1] nums[i], nums[i]) # 状态转移max_sum max(max_sum, dp[i]) # 更新最大和return max_sum方法 2分治法
def maxSubArray(nums)::type nums: List[int]:rtype: intdef divide_and_conquer(left, right):if left right:return nums[left]mid (left right) // 2# 分别求解左右部分的最大子数组和left_max divide_and_conquer(left, mid)right_max divide_and_conquer(mid 1, right)# 求解跨越中间的最大子数组和left_sum nums[mid]right_sum nums[mid 1]temp left_sumfor i in range(mid - 1, left - 1, -1):temp nums[i]left_sum max(left_sum, temp)temp right_sumfor i in range(mid 2, right 1):temp nums[i]right_sum max(right_sum, temp)cross_max left_sum right_sum# 返回左部分、右部分和跨越中间的最大值return max(left_max, right_max, cross_max)return divide_and_conquer(0, len(nums) - 1)代码解析
动态规划 初始化 dp[0] 表示以 nums[0] 结尾的子数组的最大和初始化为 nums[0]。max_sum 初始化为 dp[0]。 状态转移 对于每个 i计算 dp[i]表示以 nums[i] 结尾的子数组的最大和。如果 dp[i-1] nums[i] 比 nums[i] 大则继续扩展子数组否则从 nums[i] 重新开始。 更新最大和 每次计算 dp[i] 后更新 max_sum。 返回结果 返回 max_sum。
分治法 递归终止条件 如果 left right返回 nums[left]。 递归求解左右部分 分别递归求解左部分和右部分的最大子数组和。 求解跨越中间的最大子数组和 从中间向左右扩展求解跨越中间的最大子数组和。 返回最大值 返回左部分、右部分和跨越中间的最大值。 复杂度分析 时间复杂度 动态规划O(n)其中 n 是数组的长度。我们只需要遍历数组一次。分治法O(n log n)每次递归将数组分成两部分递归深度为 log n每层需要 O(n) 的时间求解跨越中间的最大子数组和。 空间复杂度 动态规划O(n)需要额外的 dp 数组。分治法O(log n)递归调用栈的深度为 log n。 示例运行
示例 1
# 输入nums [-2,1,-3,4,-1,2,1,-5,4]
nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums)) # 输出: 6示例 2
# 输入nums [1]
nums [1]
print(maxSubArray(nums)) # 输出: 1示例 3
# 输入nums [5,4,-1,7,8]
nums [5, 4, -1, 7, 8]
print(maxSubArray(nums)) # 输出: 23总结
通过动态规划或分治法我们可以高效地找到最大子数组和。动态规划的时间复杂度为 O(n)是最优的解法分治法的时间复杂度为 O(n log n)适合理解分治思想。希望这篇题解对你有帮助如果还有其他问题欢迎继续提问
关注我获取更多算法题解和编程技巧
