第12章：分治（Divide & Conquer）

Vol 2：算法森林探险 · 分治特辑

---

元数据卡 | 难度: 进阶 | 前置: 递归、数组、排序 | 关键词: 分治三步法 | 预计阅读: 50 分钟

---

你已经在第9章学会了归并排序——切开、排序、合并。你早就用过分治了，只是没给它起名字。核心直觉：大问题拆成小问题，小问题独立解决，组合回去。

---

分治三步法

1. 分（Divide）：将问题分解为若干子问题
2. 治（Conquer）：递归解决每个子问题
3. 合（Combine）：将子问题的解组合起来

---

1.1 最大子数组

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

暴力法 O(n^2)——枚举每个起点终点。分治法拉到 O(n log n)。

分：从中点切开 -> 左边 + 右边
治：递归求左右的最大子数组
合：还有第三种可能——跨中点的子数组
答案 = max(左最大, 右最大, 跨中点最大)

Python 实现

def max_subarray_divide_conquer(nums):
    def helper(left, right):
        if left == right:
            return nums[left]

        mid = (left + right) // 2

        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)

        left_sum = float('-inf')
        cur_sum = 0
        for i in range(mid, left - 1, -1):
            cur_sum += nums[i]
            left_sum = max(left_sum, cur_sum)

        right_sum = float('-inf')
        cur_sum = 0
        for i in range(mid + 1, right + 1):
            cur_sum += nums[i]
            right_sum = max(right_sum, cur_sum)

        cross_sum = left_sum + right_sum
        return max(left_max, right_max, cross_sum)

    return helper(0, len(nums) - 1)


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_divide_conquer(nums))

运行步骤： 保存为 max_subarray.py，执行 python max_subarray.py

预期输出： 6（子数组 [4, -1, 2, 1]）

为什么跨中点只从中点左右扩展？ 如果最大子数组在左半没延伸到 mid，它完全属于左子问题，会被递归解决。跨中点方案只需从中点左右扩展。

等等——有 O(n) 的 Kadane 算法，为什么还学分治？学这个不是为了解决这个问题，而是为理解分治思维。同一个结构在逆序对上威力更大。

---

1.2 逆序对

给定数组 [2, 4, 1, 3, 5]，计算有多少对 (i, j) 满足 i < j 且 nums[i] > nums[j]。上例共 3 对。

暴力法 O(n^2)。分治能到 O(n log n)。关键洞察：归并排序合并时，左半元素大于右半元素时，左半剩余所有元素都与这个右半元素构成逆序对。

Python 实现

def count_inversions(nums):
    def sort_and_count(arr, temp, left, right):
        if left >= right:
            return 0

        mid = (left + right) // 2
        count = 0

        count += sort_and_count(arr, temp, left, mid)
        count += sort_and_count(arr, temp, mid + 1, right)

        i, j, k = left, mid + 1, left
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                count += (mid - i + 1)
                temp[k] = arr[j]
                j += 1
            k += 1

        while i <= mid:
            temp[k] = arr[i]; i += 1; k += 1
        while j <= right:
            temp[k] = arr[j]; j += 1; k += 1

        for i in range(left, right + 1):
            arr[i] = temp[i]

        return count

    n = len(nums)
    return sort_and_count(nums, [0] * n, 0, n - 1)


nums = [2, 4, 1, 3, 5]
print(count_inversions(nums))

运行步骤： 保存为 inversions.py，执行 python inversions.py

预期输出： 3

关键行： count += (mid - i + 1)。左右两半各自有序，当 arr[j] < arr[i] 时，arr[i..mid] 全部大于 arr[j]。arr[j] 与左半所有未处理元素都构成逆序对，共 mid - i + 1 个。

---

常见陷阱

子问题必须独立

分治不是「递归」的同义词。子问题之间不能重叠。 归并排序的子问题独立；最大子数组的子问题部分重叠，但我们在「合」中额外处理了。重叠严重时（比如斐波那契数列）会退化，这正是动态规划出场的原因。

分治 vs 回溯 vs DP

• 分治：子问题独立，求解再合并
• 回溯：试所有可能路径，走不通回头
• 动态规划：有重叠子问题，存起来避免重复计算

---

验收标准

• [ ] 能徒手写出分治三步法（分-治-合）
• [ ] 能实现最大子数组问题的分治解法
• [ ] 能解释 mid - i + 1 为什么成立
• [ ] 能判断一个问题适不适合用分治

---

旅人笔记

• 分治让你从另一个视角看问题：切一刀，看两侧，再考虑跨接。
• 逆序对是分治最漂亮的附加价值案例，排序的同时顺手统计了逆序数。

一句话：分治切到单，合并是关键。

---

下一站预告

分治是把问题切成独立的小块。但很多问题不能这么切——你需要系统性试错，走不通就回头。

继续阅读：回溯 ->