12.1 分治
归并排序留下的问题
分治通常包含三步：
- 分：把规模为 n 的问题拆成更小的子问题；
- 治：递归求解，直到抵达可直接回答的基线；
- 合：把子结果组合为当前问题的答案。
“使用递归”不自动等于分治。若子问题大量重叠，直接递归会反复计算同一状态；这时可以考虑用记忆化或动态规划复用结果。若没有明确的合并规则，切开也不会凭空产生答案。
一份可执行的实现
最大子数组接收可按下标访问的整数序列，要求至少包含一个元素：空输入抛 ValueError，非整数元素抛 TypeError。整数加法让不同分组得到同一个精确和；浮点舍入或 NaN 需要另订合同。逆序对函数接收可迭代对象，先复制输入再归并；元素的 < 必须给出一致的顺序，不接受 NaN 这类无序值，函数不会额外验证整个比较关系。两个函数都不修改输入。
def max_subarray_sum(values):
if not values:
raise ValueError("max_subarray_sum requires a non-empty input")
if any(not isinstance(value, int) for value in values):
raise TypeError("values must contain integers")
def solve(left, right):
if left == right:
return values[left]
middle = (left + right) // 2
best_left = solve(left, middle)
best_right = solve(middle + 1, right)
running = 0
crossing_left = float("-inf")
for index in range(middle, left - 1, -1):
running += values[index]
crossing_left = max(crossing_left, running)
running = 0
crossing_right = float("-inf")
for index in range(middle + 1, right + 1):
running += values[index]
crossing_right = max(crossing_right, running)
return max(best_left, best_right, crossing_left + crossing_right)
return solve(0, len(values) - 1)
def count_inversions(values):
working = list(values)
buffer = [None] * len(working)
def sort_and_count(left, right):
if right - left <= 1:
return 0
middle = (left + right) // 2
inversions = sort_and_count(left, middle)
inversions += sort_and_count(middle, right)
left_index = left
right_index = middle
output = left
while left_index < middle and right_index < right:
if not working[right_index] < working[left_index]:
buffer[output] = working[left_index]
left_index += 1
else:
buffer[output] = working[right_index]
right_index += 1
inversions += middle - left_index
output += 1
while left_index < middle:
buffer[output] = working[left_index]
left_index += 1
output += 1
while right_index < right:
buffer[output] = working[right_index]
right_index += 1
output += 1
working[left:right] = buffer[left:right]
return inversions
return sort_and_count(0, len(working))
if __name__ == "__main__":
values = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
assert max_subarray_sum(values) == 6
assert max_subarray_sum([-5]) == -5
assert max_subarray_sum([-8, -3, -6]) == -3
sample = [2, 4, 1, 3, 5]
assert count_inversions(sample) == 3
assert sample == [2, 4, 1, 3, 5]
assert count_inversions([]) == 0
assert count_inversions([2, 2, 1]) == 2
print("分治检查通过")最大子数组：合并时补上跨界候选
最大和连续子数组只有三种位置：
- 完全位于左半；
- 完全位于右半；
- 穿过中点。
前两种由递归返回。跨中点的连续子数组必须包含 middle 与 middle+1，所以从中点向左找最大后缀和，再从中点右侧向右找最大前缀和，两者相加即可。
左右递归子问题并不重叠；跨界候选属于合并步骤。每层合并总共扫描 O(n) 个元素，递归式是：
T(n) = 2T(n/2) + Theta(n) = Theta(n log n)该实现只返回一个和，递归栈为 O(log n)，没有按层复制子数组。这里按整数加法和比较各花常数时间计数；大整数还要计入位数成本。递归式将左右规模简写为 n/2，非二次幂长度实际取上下整，不影响结论。
这个问题另有 Θ(n) 的 Kadane 算法。这里学习分治不是为了宣称它最快，而是练习“子答案不足时，合并步骤还缺哪类候选”。
逆序对：排序时顺手计数
逆序对是下标 i < j 且 values[i] > values[j] 的一对元素。左右两半各自排好以后，若右侧当前值小于左侧当前值，那么左半从 left_index 到 middle-1 的所有剩余值都更大：
新增逆序对数 = middle - left_index相等值不构成逆序，因此条件 not right < left 在右值不更小时先取左侧，只要求元素实现 <。每个元素在每层合并中处理一次，n ≥ 2 时总时间 Θ(n log n)，辅助空间 O(n)，递归栈 O(log n)。切片赋值还会创建临时切片，但峰值空间仍为 O(n)；空输入与单元素输入均返回 0。可以对照 Princeton 的逆序对实现核对计数定义。
Python 整数不会因计数过大溢出；固定宽度语言处理大数组时，应确认逆序对最大值 n(n-1)/2 是否超出整数类型。
分治、回溯与动态规划
| 方法 | 子问题关系 | 当前层做什么 | 典型风险 |
|---|---|---|---|
| 分治 | 通常独立 | 合并子答案 | 合并成本过高 |
| 回溯 | 枚举选择树的分支 | 做选择、递归、撤销 | 状态未恢复或组合爆炸 |
| 动态规划 | 状态大量重叠 | 缓存并复用子答案 | 状态定义或转移遗漏 |
边界并非由语法决定。同一个问题可以有多种算法；判断依据是子问题结构、输出要求与复杂度，而不是函数里是否出现递归调用。
动手检查合并步骤
- 手算
[2, 4, 1, 3, 5]的三层归并，并标出每次新增逆序对。 - 用 O(n²) 暴力实现给随机短数组做测试 oracle。
- 修改最大子数组函数，让它同时返回起止下标；相等最大和采用什么决胜规则？
- 解释为什么全负数组不能把跨界初值设为 0。
- 比较 Kadane 与分治版本：它们维护的中间信息分别是什么？
合并规则决定算法
分治的辨识点不是“代码递归了”，而是子问题能否分别求解，以及当前层能否用受控成本合成答案。最大子数组在合并时补跨界候选；逆序对在有序合并时批量计数。两者都把原本平方级的枚举改造成层数与每层工作量的乘积。
下一篇沿另一种递归树前进：回溯不合并两个独立答案，而是在选择树上做决定、检查约束并撤销状态。