---
tags: ["LeetCode", "动态规划", "分治", "中等"]
create time: 2026-05-14 12:30
---

# 13-最大子数组和

## 题面

> **LeetCode 53. Maximum Subarray**

给你一个整数数组 `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`

---

## 思路

> [!question] 💡 思考

假设你正在炒股，每天的价格变化就是 `nums` 中的一天的"涨跌幅"。你从某一天买入、某一天卖出（必须持有完整一段连续的交易日），想要让收益最大化——这个问题本质上就是在找一个连续子数组使其和最大。

最暴力的做法：枚举所有可能的子数组 `(i, j)`，共 O(n²) 对，每对求和 O(n)，总体 O(n³)。即使预处理前缀和优化到 O(1) 求和，也有 O(n²) 对组合。**有没有办法在只扫一遍数组时就得到答案？**

> [!tip] 🔑 直觉突破口：局部最优能否推动全局最优？

考虑从左往右扫描数组，走到位置 `i` 时我们面临一个抉择：

> 把 `nums[i]` 接到前面那段子数组后面更有利，还是自己另起一段更有利？

如果前面那段子数组的和是正数，加上它能让当前值更大——**接过去**；如果是负数，反而拖累——**扔掉，自己单干**。

这正是 **动态规划** 的核心思想。

### 方法一：Kadane 算法 ⭐（O(n)）

> [!abstract] 📐 状态定义

令 `dp[i]` 表示**以 `nums[i]` 结尾的最大子数组和**。注意约束："必须以 `i` 结尾"——这个限制让问题变得可转移。

> [!abstract] 🔄 状态转移方程

对于每个位置 `i`：

```
dp[i] = max(dp[i-1] + nums[i],  nums[i])
     = max(dp[i-1], 0) + nums[i]
```

两条路选优：
1. **续接上前面的**：`dp[i-1] + nums[i]`——前面的子数组对当前贡献了正值
2. **重新开始**：`nums[i]`——前面的都是负累赘，不如从当前位置新建子数组

最终答案是所有 `dp[i]` 中的最大值——因为最大子数组必然以某个位置结尾。

> [!step] 伪代码总览
>
> 1. `maxSoFar = nums[0]` — 记录历史全局最优
> 2. `currentSum = nums[0]` — 记录以当前位置结尾的最优子数组和
> 3. 遍历 `i` 从 `1` 到 `n-1`：
>    - 决定去留：`currentSum = max(currentSum, 0) + nums[i]`
>    - 刷新历史最优：`maxSoFar = max(maxSoFar, currentSum)`
> 4. 返回 `maxSoFar`

使用 Mermaid 图表示决策流程：

```mermaid
flowchart TD
    Start(["开始"]) --> Init["初始化<br/>maxSoFar = nums[0]<br/>currentSum = nums[0]"]
    Init --> Loop{"i < n?"}
    Loop -- 否 --> ReturnMax["return maxSoFar"]
    Loop -- 是 --> Decision{currentSum > 0?}
    Decision -- 是 --> Extend["续接: currentSum += nums[i]"]
    Decision -- 否 --> Reset["重置: currentSum = nums[i]"]
    Extend --> Update{"Update"}
    Reset --> Update
    Update --> CheckMax{currentSum > maxSoFar?}
    CheckMax -- 是 --> SetMax["maxSoFar = currentSum"]
    CheckMax -- 否 --> NextI["i++"]
    SetMax --> NextI
    NextI --> Loop
    ReturnMax --> End(["结束"])
```

### 逐步跟踪演示

以 `nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]` 为例：

| i | nums[i] | currentSum 决策 | currentSum 值 | maxSoFar | 解读 |
|---|---------|---------------|-------------|----------|------|
| 0 | -2 | 初始化 | -2 | -2 | 起点 |
| 1 | 1 | -2 ≤ 0 → 重置 | 1 | 1 | 前面太烂，从 1 重新开局 |
| 2 | -3 | 1 > 0 → 续接 | -2 | 1 | 收到负值但还没打破最优 |
| 3 | 4 | -2 ≤ 0 → 重置 | 4 | 4 | 再重置！这次迎来了新纪录 |
| 4 | -1 | 4 > 0 → 续接 | 3 | 4 | 被拖低了一点，仍小于历史最优 |
| 5 | 2 | 3 > 0 → 续接 | 5 | **5** ✅ | 追上并超越！|
| 6 | 1 | 5 > 0 → 续接 | **6** | **6** ✅ | 继续加码，新高！|
| 7 | -5 | 6 > 0 → 续接 | 1 | 6 | 遭遇暴击，暂退 |
| 8 | 4 | 1 > 0 → 续接 | 5 | 6 | 反弹但未超越 |

最终答案：**6**，对应子数组 `[4, -1, 2, 1]`。

> [!note] 📌 空间优化

注意到 `dp[i]` 只依赖 `dp[i-1]`，所以不需要维护整个 `dp` 数组，只需一个变量 `currentSum` 滚动更新即可。空间复杂度从 O(n) 降至 **O(1)**。

### 方法二：分治法（进阶）（O(n log n)）

题目提到了"进阶：尝试用分治法求解"。为什么一个 O(n log n) 的方法值得学？因为它提供了一个不同视角——当数据分布在多台机器上时，分治的天然并行性很有价值。

> [!question] 💡 关键问题

对于一个区间 `[left, right]`，最大子数组可能出现在哪里？只有三种情况：

1. **完全在左半部分** —— 递归求解左边
2. **完全在右半部分** —— 递归求解右边
3. **横跨中点** —— 跨越左右两部分的特殊情形

第三种情况是最需要巧妙处理的。

> [!step] 跨中点最大和的计算

要算穿过 `mid` 的最大子数组和：
- 向左扩展：从中点往左累加，记录过程中达到的最大前缀和
- 向右扩展：从中点+1 往右累加，记录过程中达到的最大后缀和
- 两者相加即为跨中点的最大和

```mermaid
flowchart LR
    A["[left ... mid | mid+1 ... right]"] --> Split["分成左右两半"]
    Split --> L["递归: 左半最大子数组"]
    Split --> R["递归: 右半最大子数组"]
    Split --> M["计算: 跨中点最大子数组"]
    L --> Merge["取三者最大值"]
    R --> Merge
    M --> Merge
    Merge --> Result["return max(L, R, M)"]
```

> [!example] 🔀 关联变体题

- **LeetCode 918. Maximum Sum Circular Subarray** — 允许循环，需要同时考虑"正常最大子数组"和"环绕最大子数组（总和 − 最小子数组）"两种情况。
- **LeetCode 1186. Maximum Subarray Sum with One Deletion** — 允许删掉最多一个元素后的最大子数组和，状态要多开一维记录"是否已删除"。
- **LeetCode 84/85. Largest Rectangle/Histogram** — 同样是经典 DP + 单调栈组合，锻炼类似的区间思维。

> [!info] 📊 两种方法对比

| 维度 | Kadane 算法 | 分治法 |
|------|-----------|--------|
| 时间复杂度 | O(n) | O(n log n) |
| 空间复杂度 | O(1) | O(log n)（递归栈）|
| 是否在线 | ✅ 流式处理，边读边算 | ❌ 需要完整数据 |
| 可扩展性 | 适合单机 | 天然适合分布式场景 |
| 实现难度 | 极简 | 需处理跨中点逻辑 |

> [!warning] ⚠️ 常见陷阱

> 全负数数组怎么办？比如 `[-3, -1, -5]`。
>
> Kadane 算法的答案应该是 **-1**（单个元素 `-1` 的子数组），而不是 0。确保初始值设为 `nums[0]`，而非 `0`。如果初始化为 0，遇到全负数时会错误地返回 0（相当于选择了空子数组），而题目明确要求子数组至少包含一个元素。

---

## 代码提示

> [!abstract] 📝 Go 伪代码框架（Kadane 算法）

```go
func maxSubArray(nums []int) int {
    maxSoFar := nums[0]
    currentSum := nums[0]

    for i := 1; i < len(nums); i++ {
        // 去留决策：前面的和对当前有帮助就接上，否则重置
        if currentSum > 0 {
            currentSum += nums[i]
        } else {
            currentSum = nums[i]
        }
        maxSoFar = max(maxSoFar, currentSum)
    }

    return maxSoFar
}
```

---

## 技巧

> [!tip] 🔑 核心模式：线性扫描 + 贪心决策

这道题的本质是 **"以每个位置为结尾的子数组最优解"** 可以高效地从上一个位置推导出。关键在于两个观察：

1. **约束结尾位置**：让 dp 定义更紧，转移就更容易写
2. **正贡献保留、负贡献丢弃**：如果之前的累积和为正，它一定有助于放大当前值

> [!note] 🐹 Go 中的细节

- Go 标准库没有内置 `max/min`（Go 1.21 之前），需要使用手写函数或条件表达式：

```go
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

- Go 1.21+ 引入了内建 `max` / `min`，可以直接调用：`max(a, b)`。
- 如果遇到全负数场景，**千万不要**把 `currentSum` 初始化为 0，必须初始化为 `nums[0]`，这样能保证至少选择一个元素。

> [!success] ✅ 记忆口诀

> 前缀为正就牵手，前缀为负就分手。  
> 一路走一路记住最高峰。

---

## 代码

```go
// maxSubArray 返回 nums 的最大子数组和（Kadane 算法）。
// 要求子数组至少包含一个元素。
func maxSubArray(nums []int) int {
	// ── Step 1: 边界与初始化 ──
	n := len(nums)
	if n == 0 {
		return 0 // 题目保证 n >= 1，防御性编程
	}

	maxSoFar := nums[0] // 历史全局最优
	currentSum := nums[0] // 以当前位置结尾的最优子数组和

	// ── Step 2: 从左往右线性扫描 ──
	for i := 1; i < n; i++ {

		// ═══ 贪心决策：前面的累积和是否为正？ ═══
		// 如果 currentSum > 0，说明之前的子数组对当前有"正向加成"——续上去
		// 如果 currentSum ≤ 0，说明之前的只会拖累——干脆从零开始
		if currentSum > 0 {
			currentSum += nums[i]
		} else {
			currentSum = nums[i]
		}

		// ═══ 刷新全局最优记录 ═══
		// 每次更新完 currentSum 后都与历史峰值比较
		if currentSum > maxSoFar {
			maxSoFar = currentSum
		}
	}

	// ── Step 3: 返回结果 ──
	return maxSoFar
}
```

> [!success] ✅ 运行验证

这是 LeetCode 第 53 题，被称为"动态规划的入门第一题"。虽然标签是中等，但它的核心思想非常优雅——一次扫描、常数空间、O(n) 时间。

- **运行时间**：约 4~7 ms（Go，击败 ~90%+ 提交）
- **空间消耗**：O(1)，仅两个变量
- **面试表现**：极高。这是一道经典的白板题，面试官常要求现场手写出 Kadane 算法并分析全负数边界

> [!quote] 💬 延伸思考

分治法的 O(n log n) 解法虽然在时间上不如 Kadane，但它启发了一个重要概念：**归并排序式的区间划分**。当数据存储在多个节点上时，每个节点可以先算出自己的局部最优，然后合并时处理跨节点的情况——这正是大规模数据处理中的经典范式。如果你感兴趣，可以尝试实现分治版本作为练习。