---
title: 深入解析经典算法题：最大子数组和的多种解法与Kadane算法最优实践，从暴力到分治再到动态规划详解
created: 2026-03-06
updated: 2026-03-06
type: summary
tags: ["algorithm", "dynamic", "kadane", "notes", "telegram"]
external: http://go/ui/posts/2120/
status: inbox
---

好的，我们来一起解析这道经典的算法题——最大子数组和。别担心，我会用你能理解的方式，一步步带你从简单的方法想到最优解。

## 题目理解

题目给了一个整数数组 `nums`，要求我们找出**连续的一段子数组**（也就是原数组中连续的一部分），使得这个子数组里所有数的和最大，并返回这个最大的和。

比如：
- 输入：`[-2,1,-3,4,-1,2,1,-5,4]`
- 输出：`6`，因为子数组 `[4,-1,2,1]` 的和是 `4 + (-1) + 2 + 1 = 6`，没有其他连续子数组的和比它大。

注意：子数组至少要包含一个数，不能为空。

## 思路分析

### 方法一：暴力枚举（最直接，但慢）

最朴素的想法：把所有可能的连续子数组都找出来，分别求和，然后找出最大的和。

怎么枚举？用两个循环：
- 外层循环固定子数组的起始位置 `i`
- 内层循环固定子数组的结束位置 `j`（从 `i` 到末尾）
- 对每个 `[i, j]` 求和，更新最大值。

但这样计算量有多大？假设数组长度为 `n`，子数组个数大约是 `n*(n+1)/2`，每个求和又需要遍历一次，所以总时间复杂度是 **O(n³)**，显然太慢。即使我们优化求和过程（比如用前缀和），也需要 **O(n²)**，对于 `n` 最大 10^5 来说，还是无法承受。

所以我们需要更聪明的方法。

### 方法二：动态规划（Kadane 算法）—— O(n) 最优解

这个算法的思想非常巧妙，它告诉我们：**我们不需要考虑所有子数组，只需要在遍历数组的过程中，记录“以当前位置结尾的最大子数组和”**。

定义：
- 设 `dp[i]` 表示以第 `i` 个元素结尾的连续子数组的最大和。
- 那么对于 `dp[i]`，要么它自己单独成一个子数组（即 `nums[i]`），要么它和前面的子数组连在一起（即 `dp[i-1] + nums[i]`）。我们取两者中较大的：
  ```
  dp[i] = max(nums[i], dp[i-1] + nums[i])
  ```
- 最后，答案就是所有 `dp[i]` 中的最大值。

举个例子，数组 `[-2,1,-3,4,-1,2,1,-5,4]`：
- i=0: dp[0] = -2
- i=1: dp[1] = max(1, -2+1) = max(1, -1) = 1
- i=2: dp[2] = max(-3, 1-3) = max(-3, -2) = -2
- i=3: dp[3] = max(4, -2+4) = max(4, 2) = 4
- i=4: dp[4] = max(-1, 4-1) = max(-1, 3) = 3
- i=5: dp[5] = max(2, 3+2) = max(2, 5) = 5
- i=6: dp[6] = max(1, 5+1) = max(1, 6) = 6
- i=7: dp[7] = max(-5, 6-5) = max(-5, 1) = 1
- i=8: dp[8] = max(4, 1+4) = max(4, 5) = 5

最大值是 6，对应 dp[6]。

我们并不需要真的用一个数组存 dp，只需要一个变量记录前一个 dp 值，另一个变量记录全局最大和即可。这就是经典的 **Kadane 算法**。

#### 代码实现（Python）：
```python
def maxSubArray(nums):
    current_max = global_max = nums[0]
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        global_max = max(global_max, current_max)
    return global_max
```

时间复杂度：O(n)，空间复杂度：O(1)。

### 方法三：分治法（更巧妙，但稍慢）

题目还提到了分治方法。分治法的核心思想是**把数组分成两半，分别求左右两半的最大子数组和，再求跨越中点的最大子数组和，然后取三者最大值**。

为什么可以这样？因为最大子数组要么完全在左边，要么完全在右边，要么跨越中间（即一部分在左边，一部分在右边）。

具体步骤：
1. 递归计算左半部分的最大子数组和 `left_max`。
2. 递归计算右半部分的最大子数组和 `right_max`。
3. 计算跨越中点的最大子数组和：
   - 从中点向左遍历，累加，记录能得到的最大和 `left_sum`。
   - 从中点向右遍历，累加，记录能得到的最大和 `right_sum`。
   - 跨越中点的和就是 `left_sum + right_sum`（注意中点元素被加了两次？其实我们是从中点往左，包含中点；再往右，不重复包含中点，所以最后相加就是整个跨越的数组和。正确做法：向左扩展到最大，向右扩展到最大，然后相加，因为中点被包含在左边或右边，但这里我们计算左半部分时包含了中点，右半部分不包含中点，或者反过来，总之要保证中点只加一次。常见写法：从中点向左计算最大和时包含中点，从中点+1向右计算最大和时不包含中点，然后相加。）
4. 返回 `max(left_max, right_max, cross_max)`。

递归的终止条件是子数组只有一个元素。

#### 举个例子：
数组 `[-2,1,-3,4,-1,2,1,-5,4]`，中点是 4（下标3）。左半部分 [-2,1,-3,4] 的最大子数组是 [4] 和为 4，右半部分 [-1,2,1,-5,4] 的最大子数组是 [4]？不对，右半部分最大应该是 [2,1]? 等等，我们递归会正确计算。跨越中点的最大和：从中点向左扩展，包含中点的最大连续和是 4（因为 4 本身，加上左边的 -3 会变小，所以只取 4）；从中点+1向右扩展，最大连续和是 2+1=3（从 -1 开始？实际上要从下标4开始向右，累加得 -1, 1, 2, -3, 1，最大的是 2+1=3 在中间某段？但这里我们要的是以中点+1为起点的连续和？正确的跨中点求法是：从中点向左，找到包含中点的最大连续和（即从某个位置到中点的和最大）；从中点+1向右，找到从中点+1开始的连续最大和（即从某个位置到右边某处的和最大）。所以这里左边最大是 4，右边最大是 2+1=3，加起来 7，但实际全局最大是 6，说明跨中点不是最大的。最后比较三者，取最大。

#### 代码实现（Python）：
```python
def maxSubArray(nums):
    def divide_and_conquer(l, r):
        if l == r:
            return nums[l]
        mid = (l + r) // 2
        # 左边最大
        left_max = divide_and_conquer(l, mid)
        # 右边最大
        right_max = divide_and_conquer(mid+1, r)
        # 跨中点最大
        # 向左扩展
        left_sum = float('-inf')
        cur = 0
        for i in range(mid, l-1, -1):
            cur += nums[i]
            left_sum = max(left_sum, cur)
        # 向右扩展
        right_sum = float('-inf')
        cur = 0
        for i in range(mid+1, r+1):
            cur += nums[i]
            right_sum = max(right_sum, cur)
        cross_max = left_sum + right_sum
        return max(left_max, right_max, cross_max)
    
    return divide_and_conquer(0, len(nums)-1)
```

时间复杂度：O(n log n)（每层递归遍历一次，共 log n 层），空间复杂度 O(log n) 递归栈。

虽然不如 Kadane 算法快，但这种分治思想在很多问题中很有用。

## 总结对比

- **暴力法**：容易想到，但太慢，不实用。
- **Kadane 算法**：O(n) 时间，O(1) 空间，最简单高效，面试必会。
- **分治法**：O(n log n)，思路巧妙，体现了“分而治之”的思想，可以作为进阶学习。

对于这道题，Kadane 算法是最佳选择，但理解分治法能帮你打开思路，应对更复杂的问题。

希望这个解析对你有帮助！如果有哪里不清楚，随时可以问我。自己动手在纸上模拟一下例子，会理解得更深刻哦。
