53. 最大子数组和 (Medium)
专题归类： 数组 · 动态规划 LeetCode 链接： https://leetcode.cn/problems/maximum-subarray/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 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 <= 10^5-10^4 <= nums[i] <= 10^4- 子数组最少包含一个元素，是连续的
题目详细分析
数据范围分析：
- 数组长度最大 10^5，O(n^2) 不可行，需要 O(n) 或 O(n log n) 的算法。
- 元素值范围 -10^4 ~ 10
输入输出特征：
- 输入是整数数组，输出是一个整数（最大子数组和）。
- 子数组必须连续，不是子序列（子序列可以跳过元素）。
- 至少包含一个元素，所以答案不可能是空数组。
边界条件：
- 数组只有一个元素 → 答案就是该元素本身。
- 数组全部为负数 → 答案是最大的那个负数（不能选空数组）。
- 数组全部为正数 → 答案是整个数组的和。
- 最大子数组可能跨越数组的多个部分，包含正数和负数。
隐藏条件：
- 负数的存在是解题的关键。负数会降低和，所以当累加和变成负数时，它对后续元素只有拖累作用，应该丢弃重来。
- 问题等价于：在遍历过程中，决定每个元素是加入之前的子数组还是重新开始。
小白版直白理解
想象你在玩一个”捡金币”游戏。路上有一排格子，每个格子里有金币（正数）或陷阱（负数）。你必须连续走一段路，不能跳着走。
你的目标是：选一段连续的路，让你捡到的金币总和最大。
直觉：
- 遇到金币肯定要捡，因为赚了。
- 遇到陷阱就要纠结了——如果之前捡了很多金币，这点陷阱能扛过去，后面可能还有更多金币；如果之前就捡得少，这个陷阱会让你血亏，不如从这个陷阱后面重新开始。
其实这就是 Kadane 算法的核心思想：每一步都在想”是接着走还是重新开始”。
生活中的类似场景：
- 股票交易中的最大收益区间
- 连续几天的最高温度上升幅度
- 比赛中状态最好的连续场次
解题思路
思路一：Kadane 算法 / 动态规划（推荐）
核心洞察：
定义 dp[i] 为以 nums[i] 结尾的最大子数组和。那么对于 nums[i] 有两种选择：
- 把它接在
nums[i-1]的后面：dp[i] = dp[i-1] + nums[i] - 以它为新起点重新开始：
dp[i] = nums[i]
取两者中较大的：dp[i] = max(nums[i], dp[i-1] + nums[i])
最终答案是所有 dp[i] 中的最大值。
空间优化： 因为 dp[i] 只依赖 dp[i-1]，所以只需要一个变量 cur_sum 来滚动更新。
def maxSubArray(nums):
# cur_sum: 以当前位置结尾的最大子数组和
# max_sum: 全局最大子数组和
cur_sum = max_sum = nums[0]
for num in nums[1:]:
# 要么接上前面的，要么重新开始
cur_sum = max(num, cur_sum + num)
# 更新全局最大值
max_sum = max(max_sum, cur_sum)
return max_sum复杂度： O(n) 时间，O(1) 空间。
思路二：贪心法（同 Kadane 的另一种理解）
遍历数组，如果当前累加和 cur_sum < 0，说明它对后续没有正面贡献，直接丢弃，从下一个元素重新累加。否则继续累加。
def maxSubArray_greedy(nums):
cur_sum = 0
max_sum = nums[0]
for num in nums:
cur_sum += num
max_sum = max(max_sum, cur_sum)
# 核心：如果累加和变负，丢弃重来
if cur_sum < 0:
cur_sum = 0
return max_sum关键区别： 贪心法在 cur_sum < 0 时重置为 0（相当于丢弃），而 DP 法用 max() 选择是否重新开始。两者本质相同。
思路三：分治法（进阶）
将数组分为左右两半，最大子数组和来自三种情况：
- 完全在左半部分
- 完全在右半部分
- 跨越中点（从中点向左扩展的最大和 + 从中点向右扩展的最大和）
取三者最大值。时间复杂度 O(n log n)，空间 O(log n)。
def maxSubArray_divide(nums):
def divide_and_conquer(l, r):
if l > r:
return -float('inf')
if l == r:
return nums[l]
mid = (l + r) // 2
# 跨越中点的最大和
left_max = cur = 0
for i in range(mid - 1, l - 1, -1):
cur += nums[i]
left_max = max(left_max, cur)
right_max = cur = 0
for i in range(mid + 1, r + 1):
cur += nums[i]
right_max = max(right_max, cur)
cross_max = nums[mid] + left_max + right_max
# 取三者最大值
return max(divide_and_conquer(l, mid - 1),
divide_and_conquer(mid + 1, r),
cross_max)
return divide_and_conquer(0, len(nums) - 1)易错点
- 初始化问题：
max_sum必须初始化为nums[0]而不是 0。如果全为负数但初始化为 0 会返回错误结果 0。 - 空数组返回：题目说至少一个元素，但如果是空数组需要特殊处理。
- 重置时机：贪心法中重置
cur_sum = 0而不是重置为当前元素值——因为下一轮循环会先加上当前元素。 - 负数处理：当累加和加上一个负数后虽然变小了但不一定需要重置（后面可能有更大的正数）。
- 连续要求：记住是连续子数组，不是子序列。如果用排序就错了。
框架提炼
Kadane 算法通用模板（最大子数组和系列）：
def maxSubarrayKadane(nums):
# Step 1: 初始化
cur = nums[0] # 以当前位置结尾的子数组最大和
best = nums[0] # 全局最大和
# Step 2: 遍历
for num in nums[1:]:
# 状态转移：要么接上，要么重开
cur = max(num, cur + num)
# 更新全局最优
best = max(best, cur)
return bestKadane 变体适用场景：
- 最大子数组乘积 → 152-乘积最大子数组（需要同时维护最大和最小值，因为负数乘负数得正数）
- 最大子数组和（允许删除一个元素） → 1186-删除一次得到子数组最大和
- 环形最大子数组和 → 918-环形子数组的最大和（总数组和 - 最小子数组和）
关联题目
- 152-乘积最大子数组 — Kadane 算法的变体，区别在于乘积需要考虑负负得正，所以需要同时维护最大值和最小值。
- 918-环形子数组的最大和 — 在 Kadane 基础上扩展到环形数组，需要同时计算最大子数组和与最小子数组和。
- 560-和为 K 的子数组 — 同样是子数组问题，但用的是前缀和+哈希表而非 Kadane，因为目标和是定值 k 而非最值。
- 121-买卖股票的最佳时机 — 本质上也是找最大差值（相当于找
prices[i] - min_price的最大值），可以用 Kadane 思路理解。