LeetCode热题10053.最大子数组和

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: int """ n = len(nums) dp = [0] * n dp[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: int """ def 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_sum for i in range(mid - 1, left - 1, -1): temp += nums[i] left_sum = max(left_sum, temp) temp = right_sum for 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)，适合理解分治思想。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！