好的，我们这次来详细讲解 LeetCode 第 53 题「最大子数组和」。
这是一道非常经典的动态规划问题，也是面试中的高频题。
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. 思路分析
2.1 暴力法（不推荐，但有助于理解）
我们可以枚举所有可能的连续子数组，计算它们的和，然后取最大值。
- 子数组起点
i从 0 到 n-1 - 子数组终点
j从 i 到 n-1 - 对每个区间
[i, j]累加求和
时间复杂度：O(n³) 或优化到 O(n²)（用前缀和可到 O(n²)），但 n 很大时会超时。
2.2 动态规划思路（重点）
我们想要 O(n) 的解法。
核心问题：以第 i 个元素结尾的“最大子数组和”与前面的结果有什么关系？
设 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
那么有两种情况：
- 把
nums[i]接在前面的子数组后面：dp[i-1] + nums[i] - 从
nums[i]重新开始一个子数组：nums[i]
我们要取较大值：
dp[i] = max(nums[i], dp[i-1] + nums[i])
为什么这样设计？
因为题目要求连续子数组，所以必须以 nums[i] 结尾，才能形成连续。
那么最大和要么是前面的最大和加上当前元素，要么是当前元素自己（如果前面和是负数，加上只会更小，不如另起炉灶）。
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 | 前面是负数，不如从 1 重新开始 |
| 2 | -3 | max(-3, 1 + (-3)) = -2 | 接上前面的和 1 得到 -2，比 -3 大 |
| 3 | 4 | max(4, -2 + 4) = 4 | 前面是 -2，加上 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 |
全局最大和是 dp 数组中的最大值：max(-2, 1, -2, 4, 3, 5, 6, 1, 5) = 6。
4. 空间优化
我们不需要保存整个 dp 数组，因为 dp[i] 只依赖于 dp[i-1]。
可以用一个变量 pre 表示上一个 dp 值，一个变量 maxAns 记录全局最大值。
优化后步骤：
- 初始化
pre = 0,maxAns = nums[0] - 遍历 i 从 0 到 n-1：
pre = max(nums[i], pre + nums[i])maxAns = max(maxAns, pre)
- 返回
maxAns
5. 代码实现（Python）
def maxSubArray(nums):
pre = 0
maxAns = nums[0]
for x in nums:
pre = max(x, pre + x)
maxAns = max(maxAns, pre)
return maxAns
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
6. 分治法思路（进阶）
题目还要求用分治法，这里简要说明：
将数组从中间分成左右两部分，最大子数组和要么在：
- 左半边
- 右半边
- 横跨中间（包括中间向左延伸的最大和 + 中间向右延伸的最大和）
递归求解左右两部分，合并时计算横跨情况。
时间复杂度：O(n log n)，虽然不如 DP 高效，但是练习分治的好题目。
7. 总结
- 关键点：定义
dp[i]为以nums[i]结尾的最大子数组和，转移方程dp[i] = max(nums[i], dp[i-1] + nums[i])。 - 空间优化：只保留前一个状态，O(1) 空间。
- 思维技巧：当发现前面累加和为负数时，就放弃前面的部分，从当前元素重新开始。
这样循序渐进地理解，就能掌握这个经典的动态规划问题了。