LeetCode 第 53 题：最大子数组和（Maximum Subarray）
字数 2021 2025-10-25 17:17:03
好的，我们这次来详细讲解 LeetCode 第 53 题：最大子数组和（Maximum Subarray）。
1. 题目描述
给你一个整数数组 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
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
2. 题目理解
我们要找的是 连续子数组（不能跳着选，必须连续一段），并且它的和最大。
注意：数组可能包含负数，所以不是简单地整个数组求和，因为负数可能会让和变小。
3. 思路演进
3.1 暴力法（不可取，但有助于理解）
我们可以枚举所有可能的连续子数组，计算它们的和，然后取最大值。
- 子数组起点
i从 0 到 n-1 - 子数组终点
j从 i 到 n-1 - 对每个
(i, j)计算sum(nums[i..j])
复杂度：O(n³) 如果每次重新求和，优化一下前缀和可以到 O(n²)，但 n 很大时仍然太慢。
3.2 动态规划（Kadane 算法）思路 O(n)
核心思想是：以每个位置为结尾的最大子数组和，可以由前一个位置为结尾的最大子数组和推导出来。
定义：
dp[i]表示以第i个元素结尾的 最大子数组和。
思考：
- 如果已知
dp[i-1]（以i-1结尾的最大和），那么对于位置i：- 我可以只取
nums[i]自己（如果前面的dp[i-1]是负数，加上它只会让和变小，不如重新开始） - 或者我可以接上前面以
i-1结尾的子数组（如果dp[i-1]是正数，加上它对增大和有帮助）
- 我可以只取
所以递推公式：
\[dp[i] = \max(nums[i], \ dp[i-1] + nums[i]) \]
最后答案：
\[\max_{0 \le i < n} dp[i] \]
3.3 逐步推导示例
以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例：
| i | nums[i] | dp[i] (以 i 结尾的最大和) | 解释 |
|---|---|---|---|
| 0 | -2 | -2 | 只有自己 |
| 1 | 1 | max(1, -2+1) = 1 | 前面是 -2，不如重新从 1 开始 |
| 2 | -3 | max(-3, 1 + (-3)) = -2 | 接上前面的 1 得到 -2，比单独 -3 大 |
| 3 | 4 | max(4, -2 + 4) = 4 | 前面是 -2，加上反而小，不如从 4 开始 |
| 4 | -1 | max(-1, 4 + (-1)) = 3 | 接上 4 得 3 |
| 5 | 2 | max(2, 3 + 2) = 5 | 接上 3 得 5 |
| 6 | 1 | max(1, 5 + 1) = 6 | 接上 5 得 6（这是全局最大） |
| 7 | -5 | max(-5, 6 + (-5)) = 1 | 接上 6 得 1 |
| 8 | 4 | max(4, 1 + 4) = 5 | 接上 1 得 5 |
所以最大子数组和 = max(-2, 1, -2, 4, 3, 5, 6, 1, 5) = 6。
3.4 空间优化
因为 dp[i] 只依赖于 dp[i-1]，所以只需一个变量 current_sum 记录当前以 i 结尾的最大和，一个变量 max_sum 记录全局最大和。
4. 代码实现（Kadane 算法）
def maxSubArray(nums):
current_sum = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
# 如果 current_sum 是负数，则舍弃前面的，从当前元素重新开始
current_sum = max(nums[i], current_sum + nums[i])
# 更新最大和
max_sum = max(max_sum, current_sum)
return max_sum
5. 分治法思路（进阶）
题目要求尝试分治法，我们来看看如何分治：
将数组从中间分成左右两半，最大子数组和可能出现在：
- 完全在左半部分
- 完全在右半部分
- 跨越中间（包含中间元素向左右延伸）
递归求解：
- 左半部分最大和
- 右半部分最大和
- 跨越中点的最大和 = 中点向左延伸的最大和 + 中点向右延伸的最大和（不重复加中点）
最后取三者最大值。
复杂度：O(n log n)，虽然比 Kadane 算法慢，但体现了分治思想。
分治法代码（供参考）
def maxSubArray(nums):
def divide_conquer(left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
# 左半部分最大和
left_max = divide_conquer(left, mid)
# 右半部分最大和
right_max = divide_conquer(mid + 1, right)
# 跨越中点的最大和
# 从中点向左延伸的最大和
left_cross_max = nums[mid]
left_cross_sum = 0
for i in range(mid, left - 1, -1):
left_cross_sum += nums[i]
left_cross_max = max(left_cross_max, left_cross_sum)
# 从中点向右延伸的最大和
right_cross_max = nums[mid + 1]
right_cross_sum = 0
for i in range(mid + 1, right + 1):
right_cross_sum += nums[i]
right_cross_max = max(right_cross_max, right_cross_sum)
cross_max = left_cross_max + right_cross_max
return max(left_max, right_max, cross_max)
return divide_conquer(0, len(nums) - 1)
6. 总结
- Kadane 算法（动态规划）是本题最优解，时间复杂度 O(n)，空间 O(1)。
- 关键思路：
dp[i]表示以 i 结尾的最大子数组和，递推时判断是否舍弃前面的和。 - 分治法虽然复杂度高，但是练习分治思想的经典例题。
这样讲解清楚吗？我们可以再找一个题目继续。