分治法

分治法是用于解决复杂问题的一种重要算法思想。它的核心思路是：将一个复杂的问题分解成若干个规模较小但类似的子问题，递归解决这些子问题，然后将子问题的解合并得到原始问题的解。

分治法特别适合解决以下类型的问题：

• 可以分解成相似的子问题
• 子问题相互独立，没有重叠
• 子问题的解可以合并
• 问题规模缩小到一定程度可以很容易解决

在归并排序、快速排序、大整数乘法、最近点对问题、最大子数组和问题（本文将详细讨论）问题中，分治法都得到了很好的应用。

基本思路

分治法包含三个主要步骤：

1. 分解：将原问题分解成若干个规模较小的子问题，子问题与原问题形式相同，只是规模更小。
2. 解决：递归地解决各个子问题，当子问题足够小时，可以直接求解。
3. 合并：将子问题的解合并成原问题的解。

分治法解决最大子数组和问题

下面我们着手解决 LeetCode 53. 最大子数组和。

最大子数组和问题：给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

基本思路

分治法解决最大子数组和问题的核心思想是：把大问题分解成小问题来解决。具体来说：

假设我们有一个数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
我们要找出和最大的连续子数组。

想象我们把数组从中间切开，那么最大子数组只可能出现在三种位置：

1. 完全在左半边
   例如：[-2, 1, -3, 4]中的[4]

2. 完全在右半边
   例如：[-1, 2, 1, -5, 4]中的[2, 1]

3. 跨越中间点
   例如：[4, -1, 2, 1]，包含了左右两部分

通过递归，我们可以用相同的逻辑解决所有子问题，最后通过比较三种情况，一定能找到全局最优解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def F_寻找跨越中间点的最大子数组和(nums:list[int], left:int, mid:int, right:int):
    # 计算包含左半部分最后一个元素的最大和
    左和 = float('-inf')
    当前和 = 0
    for i in range(mid, left - 1, -1):
        当前和 += nums[i]
        左和 = max(左和, 当前和)
        
    # 计算包含右半部分第一个元素的最大和
    右和 = float('-inf')
    当前和 = 0
    for i in range(mid + 1, right + 1):
        当前和 += nums[i]
        右和 = max(右和, 当前和)
    # 返回跨越中间的最大和
    return 左和 + 右和

def 分治求解(nums:list[int], left:int, right:int):
    # 基础情况：只有一个元素
    if left == right:
        return nums[left]
    # 分解问题，这里取中间值
    mid = (left + right) // 2
    # 递归求解左右子数组
    左边最大和 = 分治求解(nums, left, mid)
    右边最大和 = 分治求解(nums, mid + 1, right)
    # 计算跨越中间的最大和
    跨越中间的最大和 = 寻找跨越中间点的最大子数组和(nums, left, mid, right)
    # 返回三种情况的最大值
    return max(左边最大和, 右边最大和, 跨越中间的最大和)

def 最大子数组和(nums:list[int]):
    # 处理边界情况
    if not nums:
        return 0
    # 调用主函数
    return 分治求解(nums, 0, len(nums) - 1)

时间复杂度分析

1. 主定理分析

算法的递归关系式为：T(n) = 2T(n/2) + O(n)
根据主定理，该情况属于第二种情况：

• a = 2（两个子问题）
• b = 2（每次将问题规模减半）
• f(n) = O(n)（合并步骤的时间复杂度）

因此，时间复杂度为 O(n log n)

2. 迭代法分析

T(n) = 2T(n/2) + cn
展开可得：
T(n) = 2(2T(n/4) + cn/2) + cn
= 4T(n/4) + 2cn
= 8T(n/8) + 3cn
…
= 2^k T(n/2^k) + kcn，其中k = log n
最终得到时间复杂度为 O(n log n)

其他解决方法比较

动态规划解法

动态规划解决最大子数组和问题的思路是：维护两个变量，一个记录当前位置的最大子数组和，另一个记录全局最大子数组和。因为这个问题里，子数组和只与前一个位置的子数组和有关，所以只需要一个变量。（也就是数组是连续的）

核心思想

对于数组中的每个元素，我们都面临两个选择：

• 将当前元素加入前面的子数组
• 以当前元素开始一个新的子数组

决策过程

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例：

当前和小于0时，表明之前的子数组和会拖累后面的元素，应该重新开始。当前和大于0时，即使很小，也可能在后续累加中变得更大。通过不断更新最大和，我们能始终保持全局最优解。

状态转移

对于位置i，状态转移方程：

1
2

当前和 = max(nums[i], 当前和 + nums[i])
最大和 = max(最大和, 当前和)

算法比较

如果追求执行效率或注重代码维护性，应选择动态规划解法。
如果需要并行计算和问题有扩展性，可以考虑分治法。

子问题的独立性

分治法适合子问题独立的情况，而动态规划适合子问题重叠的情况。因为分治法会将问题分解成多个子问题，如果子问题不独立，则需要重复计算，导致效率低下。

参考资料

• 算法通关手册
• Oi Wiki