最大子数组和（动态规划与分治）

2026/6/28 · 算法与数据结构

问题简述

1 问题背景

在金融交易市场中，投资者常常需要分析股票价格的波动以寻找最佳的买入和卖出时机。假设已知某支股票连续几日的每日价格变化量（相对于前一天的涨跌幅），投资者希望找到一段连续的时间区间，使得这段时间内价格变化的总和达到最大，从而获得最高收益。

2 问题抽象

给定一个包含 $n$ 个整数的数组，要求在其中找到一个具有最大和的连续子数组。

空间设定：输入为一个一维线性数组。
初始状态：数组中的每个元素代表每日的价格变化值（正数表示上涨，负数表示下跌）。
求解目标：找到一个子数组 nums[i..j]，使得 sum(nums[i..j]) 的值最大，并确定对应的起始索引 $i$ 和结束索引 $j$ 。

3 算法思维逻辑

解决最大子数组和问题的核心在于如何高效处理搜索空间：

规模递减：通过分治法将大数组划分为左右两个子数组，递归求解规模更小的子问题。
状态转移：利用动态规划思想，通过前一个位置的最优解推导出当前位置的最优解，避免冗余计算。
终止准则：在分治递归中，当子数组只剩一个元素时停止；在动态规划中，遍历完整个数组即结束。

4 数学表达

为了通过编程实现快速求解，建立如下递推关系。

动态规划状态转移方程：假设 $max\_ending\_here[i]$ $ma x_e n d in g_h er e [i]$ 表示以第 $i$ $i$ 个元素结尾的最大子数组和：
- $max\_ending\_here[i] = \max(nums[i], max\_ending\_here[i-1] + nums[i])$
分治法合并规则：最大和可能出现在左半部、右半部或跨越中间点：
- $cross\_max = \max\_left\_suffix + \max\_right\_prefix$

基础知识

1 分治算法

分治法是一种重要的算法设计范式。其核心思想是递归地将一个复杂问题分解为多个规模更小、类型相似的子问题，直到子问题变得足够简单可以直接求解，最后将子问题的解合并为原问题的解。

1.1 核心三步骤

一个典型的分治过程包含以下三个阶段：

分解（Divide）：将原问题 $P$ 划分为 $k$ 个规模较小的子问题 $P_1, P_2, \dots, P_k$ 。
解决（Conquer/Solve）：递归地求解各子问题。若子问题规模足够小，则直接计算。
合并（Combine）：将各子问题的解 $S_1, S_2, \dots, S_k$ 合并成原问题的解 $S$ 。

2 时间复杂度分析：主定理

当使用分治法解决问题时，其运行时间通常可以用递归方程 $T(n) = aT(n/b) + f(n)$ 表示。主定理（Master Theorem） 提供了一种通用的数学方法来快速确定这些方程的渐近复杂度。

2.1 针对划分函数（Dividing Function）的应用

对于形式为 $T(n) = aT(n/b) + f(n)$ 的递归式（其中 $a \ge 1, b > 1$ ），我们通过比较 $n^{\log_b a}$ 与 $f(n) = n^c$ 的增长速度来判定：

$\log_b a > c$ ：子问题的数量 $a$ 产生的开销远超合并开销，则： $T(n) = \Theta(n^{\log_b a})$
$\log_b a \approx c$ ：每层分解与合并的开销平衡，则： $T(n) = \Theta(n^{\log_b a} \log n)$
$\log_b a < c$ ：合并操作的开销占主要地位，则： $T(n) = \Theta(f(n))$

2.2 针对递减函数（Decreasing Function）的应用

对于形式为 $T(n) = aT(n-b) + f(n)$ 的递归式，其复杂度取决于系数 $a$ 与 $1$ 的比较：

$a > 1$ ：复杂度呈指数级增长， $T(n) = O(a^{n/b} \cdot f(n))$ 。
$a = 1$ ：复杂度呈线性或多项式增长， $T(n) = O(n \cdot f(n))$ 。
$a < 1$ ：复杂度由合并项决定， $T(n) = O(f(n))$ 。

2.3 严格推导：递归树证明

主定理的有效性可以通过递归树进行严格推导。

推导过程：
1. 将递归方程展开为求和形式： $T(n) = \sum_{i=0}^{k} a^i f(\frac{n}{b^i})$ ，其中 $k = \log_b n$ 是树的高度。
2. 令 $q = \frac{a}{b^c}$ （假设 $f(n) = n^c$ ），则方程可转化为等比数列求和： $T(n) = n^c \cdot \frac{1-q^{k+1}}{1-q}$ 。
三种结果的数学本质：
- 当 $q < 1$ ( $c > \log_b a$ )，级数收敛，首项 $n^c$ 决定结果。
- 当 $q = 1$ ( $c = \log_b a$ )，所有层开销相等，结果为 $n^c \cdot \text{height}$ 。
- 当 $q > 1$ ( $c < \log_b a$ )，最后一层叶子节点数 $n^{\log_b a}$ 决定结果。

2.4 应用实例

Karatsuba 大整数乘法 当我们需要计算两个 $n$ 位大整数 $x$ 和 $y$ 的乘积时，传统的竖式乘法需要 $O(n^2)$ 的复杂度。Karatsuba 算法通过代数变换减少了乘法操作的次数。

分解策略：将 $x$ $x$ 和 $y$ $y$ 分别拆分为高位和低位两部分：
- $x = a \cdot 10^m + b$
- $y = c \cdot 10^m + d$
- 其中 $m \approx n/2$ 。
数学展开：
- $x \cdot y = ac \cdot 10^{2m} + (ad + bc) \cdot 10^m + bd$ 。
优化逻辑：
- 直接计算：需要 4 次乘法（ $ac, ad, bc, bd$ ）。
- Karatsuba 优化：只需要 3 次 乘法：计算 $ac$ 、 $bd$ 以及 $(a+b)(c+d)$ 。
- 关键公式：利用已知的 $ac$ 和 $bd$ 来求中间项： $ad + bc = (a+b)(c+d) - ac - bd$ 。
复杂度分析：
- 递推方程： $T(n) = 3T(n/2) + O(n)$ 。
- 主定理判定：根据 $n^{\log_2 3}$ vs $n^1$ ，由于 $\log_2 3 \approx 1.585$ ，复杂度为 $O(n^{1.585})$ 。

Toom-Cook 3 算法 Toom-Cook 算法是 Karatsuba 的推广，通过将整数拆分为更多的部分来进一步降低复杂度。

分解策略：将整数拆分为 $k$ $k$ 个部分。以 Toom-3 为例，将大整数表示为二次多项式：
- $A(x) = a_2x^2 + a_1x + a_0$
- $B(x) = b_2x^2 + b_1x + b_0$
乘法过程：
- 结果为 $C(x) = A(x) \cdot B(x) = C_4x^4 + C_3x^3 + C_2x^2 + C_1x^1 + C_0$ 。
优化效果：
- 标准做法：直接进行块分解需要 $3^2 = 9$ 次乘法。
- Toom-3 优化：通过对多项式进行取点求值（Interpolation），将乘法次数减少到 5 次（公式为 $2k-1$ ）,。
复杂度分析：
- 递推方程： $T(n) = 5T(n/3) + O(n)$ 。
- 主定理判定：根据 $n^{\log_3 5}$ vs $n^1$ ，由于 $\log_3 5 \approx 1.465$ ，复杂度为 $O(n^{1.465})$ 。

Strassen 矩阵乘法 两个 $n \times n$ 矩阵 $A$ 和 $B$ 的标准乘法需要 $O(n^3)$ 的时间复杂度。Strassen 利用分治思想将矩阵划分为 $2 \times 2$ 的分块进行优化。

优化方案：Strassen 构造了 7 个中间变量 $M_1 \dots M_7$ $M_{1} \dots M_{7}$ ，每个变量只涉及 1 次 子矩阵乘法：
- $M_1 = (A_{11} + A_{22})(B_{11} + B_{22})$
- $M_2 = (A_{21} + A_{22})B_{11}$
- $M_3 = A_{11}(B_{12} - B_{22})$
- $M_4 = A_{22}(B_{21} - B_{11})$
- $M_5 = (A_{11} + A_{12})B_{22}$
- $M_6 = (A_{21} - A_{11})(B_{11} + B_{12})$
- $M_7 = (A_{12} - A_{22})(B_{21} + B_{22})$
结果合并：利用这 7 个 $M$ $M$ 值通过加减法（复杂度为 $O(n^2)$ $O (n^{2})$ ）合成结果矩阵 $C$ $C$ 的四个分块：
- $C_{11} = M_1 + M_4 - M_5 + M_7$
- $C_{12} = M_3 + M_5$
- $C_{21} = M_2 + M_4$
- $C_{22} = M_1 - M_2 + M_3 + M_6$
复杂度分析：
- 递推方程： $T(n) = 7T(n/2) + O(n^2)$ 。
- 主定理判定：比较 $n^{\log_2 7}$ （约 $n^{2.81}$ ）与合并开销 $n^2$ ，复杂度为 $O(n^{2.81})$ 。
- 对比：标准的递归矩阵乘法方程为 $T(n) = 8T(n/2) + O(n^2)$ ，复杂度为 $O(n^3)$ 。

2.5 省流表格

算法	关键技术点	乘法/分支次数减少	最终复杂度
标准大数乘法	逐位相乘	4 次 (n/2 规模)	$O(n^2)$
Karatsuba	代数恒等式替换	3 次 (n/2 规模)	$O(n^{1.585})$
Toom-Cook 3	多项式取点插值	5 次 (n/3 规模)	$O(n^{1.465})$
标准矩阵乘法	行列加权求和	8 次 (n/2 规模)	$O(n^3)$
Strassen	构造 7 个辅助中间量	7 次 (n/2 规模)	$O(n^{2.81})$

核心启示：在分治算法设计中，合并阶段（Combine）引入的加减法开销（通常是 $O(n)$ 或 $O(n^2)$ ）远远低于递归分支中的乘法开销。通过数学手段减少乘法次数（减小参数 $a$ ）是提升算法性能的最强动力。

解决思路

1 暴力与优化方案

这类方案侧重于通过枚举子数组的边界来寻找结果。

1.1 基础暴法

实现原理：通过嵌套两层循环枚举所有可能的起点 $i$ 和终点 $j$ 。
代价分析：时间复杂度为 $O(n^2)$ ，效率极低。

1.2 前缀和优化

实现原理：预先计算前缀和数组 prefix_sum。
优势：可以将任意子数组之和的计算简化为 prefix_sum[j+1] - prefix_sum[i]，虽然仍需 $O(n^2)$ 枚举，但单次计算更快。

2 动态规划方案（Kadane算法）

2.1 动态规划（Kadane算法）的状态转移推导

为了实现 $O(n)$ 的线性求解，我们需要通过子问题的最优解来构建全局最优解。

状态定义：设 $f(i)$ （或代码中的 max_ending_here）表示以第 $i$ 个元素结尾的所有连续子数组中的最大和。
逻辑拆解：对于数组中的任意位置 $i$ $i$ ，以它结尾的连续子数组必然包含 $nums[i]$ $n u m s [i]$ 。此时存在两种可能的情况：
1. 子数组只包含自己：即 $nums[i]$ 独立成为一个子数组。这种情况通常发生在之前的子数组和为负数，只会拉低当前总和时。
2. 子数组包含之前的序列：即在以 $i-1$ 结尾的最大子数组之后接上 $nums[i]$ 。其和为 $f(i-1) + nums[i]$ 。
递推公式推导：为了求得 $f(i)$ 的最大值，我们只需在上述两种情况中取较大者： $f(i) = \max(nums[i], f(i-1) + nums[i])$
全局最优解：由于最大子数组可能在数组的任何位置结尾，因此最终答案是所有 $f(i)$ 中的最大值： $\text{Max\_Sum} = \max_{0 \le i < n} \{f(i)\}$

3 分治方案

分治法通过将问题递归分解为互不重叠的子问题来解决。

实现步骤：
1. 分解：将数组从中间点一分为二。
2. 解决：递归计算左、右半部的最大子数组和。
3. 合并：计算必须跨越中点的最大和，并取三者中的最大值。

3.1 分治法（跨越中点）的合并逻辑推导

分治法的难点在于如何处理“跨越中点”的子数组，因为它们不完全属于左半部或右半部。

场景划分：给定区间 $[left, right]$ $[l e f t, r i g h t]$ 和中点 $mid = (left + right) // 2$ $mi d = (l e f t + r i g h t) //2$ 最大子数组的和 $T(left, right)$ $T (l e f t, r i g h t)$ 必然处于以下三者之一：
1. 完全在左半部： $T(left, mid)$ 。
2. 完全在右半部： $T(mid+1, right)$ 。
3. 跨越中点：即子数组包含 $nums[mid]$ 和 $nums[mid+1]$ 。
跨中点子数组的构造：一个跨越中点的子数组 $nums[i..j]$ $n u m s [i .. j]$ 可以拆分为两部分：
- 左半部分： $nums[i..mid]$ （左半部的某个后缀）。
- 右半部分： $nums[mid+1..j]$ （右半部的某个前缀）。
最优性推导：为了使跨中点的总和 $cross\_max$ $cr oss_ma x$ 最大，必须分别使左半部分的后缀和右半部分的前缀达到最大。
1. 左侧最大后缀：从 $mid$ 开始向左遍历至 $left$ ，记录出现过的最大累加和 left_cross_max。
2. 右侧最大前缀：从 $mid+1$ 开始向右遍历至 $right$ ，记录出现过的最大累加和 right_cross_max。
最终合并公式：跨越中点的最大和即为两者之和： $cross\_max = \text{left\_cross\_max} + \text{right\_cross\_max}$ 最后通过比较 $max(left\_max, right\_max, cross\_max)$ 得到当前区间的最终解。

代码实现

1 暴力法

1.1 直接暴力

def max_subarray_bruteforce(nums: List[int]) -> int:
    """
    直接暴力法：O(n^2)
    固定左边界，扩展右边界，累加计算所有子数组和。
    """
    n = len(nums)
    max_sum = float('-inf')  # 初始化负无穷，处理全负数情况
    
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]          # 逐步扩展子数组 [i..j]
            if current_sum > max_sum:
                max_sum = current_sum
                
    return max_sum

1.2 前缀和

def max_subarray_prefix(nums: List[int]) -> int:
    """
    前缀和暴力法：O(n^2)
    利用 prefix[j+1] - prefix[i] 快速获取任意子数组和。
    """
    n = len(nums)
    # 构建前缀和数组，长度为 n+1，prefix[0] = 0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    max_sum = float('-inf')
    
    for i in range(n):          # 子数组起点
        for j in range(i, n):   # 子数组终点
            # 子数组 nums[i..j] 的和
            current_sum = prefix[j + 1] - prefix[i]
            if current_sum > max_sum:
                max_sum = current_sum
                
    return max_sum

2 动态规划法

该算法通过一次遍历即可完成求解。

def max_subarray_kadane(nums: List[int]) -> int:
    """
    Kadane 算法（DP）：O(n)
    max_ending_here: 以当前元素结尾的最大子数组和
    max_so_far:     全局最大子数组和
    """

    max_so_far = nums[0]
    max_ending_here = nums[0]
    
    for i in range(1, len(nums)):
        # 核心逻辑：要么自立门户，要么加入前面的队伍
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        # 更新全局最优
        max_so_far = max(max_so_far, max_ending_here)
        
    return max_so_far

2.1 核心逻辑

利用 max_so_far 记录全局最优解，max_ending_here 记录当前位置的局部状态。

3 分治实现：基于递归的合并策略

def max_subarray_divide_conquer(nums: List[int]) -> int:
    """
    分治法：O(n log n)
    递归处理左右区间，并合并跨越中点的最大和。
    """
    
    def max_crossing_sum(left: int, mid: int, right: int) -> int:
        """
        计算跨越中点 mid 的最大子数组和。
        必须包含 nums[mid] 和 nums[mid+1]。
        """
        # 从中点向左扫描（包含 mid）
        left_sum = float('-inf')
        current = 0
        for i in range(mid, left - 1, -1):
            current += nums[i]
            if current > left_sum:
                left_sum = current
        
        # 从中点向右扫描（包含 mid+1）
        right_sum = float('-inf')
        current = 0
        for i in range(mid + 1, right + 1):
            current += nums[i]
            if current > right_sum:
                right_sum = current
        
        # 跨中点最大和 = 左半部分最大（必须包含 mid）+ 右半部分最大（必须包含 mid+1）
        return left_sum + right_sum
    
    def divide_and_conquer(left: int, right: int) -> int:
        """递归处理区间 [left, right]"""
        # 递归基：只有一个元素
        if left == right:
            return nums[left]
        
        # 分
        mid = (left + right) // 2
        
        # 治（递归求解左右两半）
        left_max = divide_and_conquer(left, mid)
        right_max = divide_and_conquer(mid + 1, right)
        
        # 合（计算跨中点情况）
        cross_max = max_crossing_sum(left, mid, right)
        
        # 返回三者最大值
        return max(left_max, right_max, cross_max)

3.1 递归函数定义

定义 divide_and_conquer(left, right) 处理指定区间的子问题。

分析与总结

算法对比

维度	暴力	分治法	动态规划	备注
时间效率	$O(n^2)$	$O(n \log n)$	$O(n)$	DP 在线性时间内完成。
空间效率	$O(1)$	$O(\log n)$	$O(1)$	分治法涉及递归调用的栈内存。
编程难度	低	中	中	分治法需处理跨越中点的特殊逻辑。
子问题性质	N/A	独立	重叠	DP通过存储重叠子问题结果避免冗余。