分治算法：把大问题拆成小问题，轻松搞定！

你有没有遇到过这样的难题——桌上一堆乱糟糟的乐高零件，要拼出一个大城堡，不知道从哪下手？聪明的方法是：先按颜色分成几堆，每堆拼一个小部分，最后再把小部分组合起来。这就是分治（Divide and Conquer）的核心思想：“分而治之”。在编程里，分治算法能把一个复杂的大问题，拆成若干个结构相同的小问题，分别解决后，再把小问题的答案合并起来，得到最终结果。

比如，你想知道全班有多少人。老师可以先把班级分成4个小组，每组数完人数，再把4个数字加起来，就是全班总人数。分治就是这种“先分、再算、最后合”的套路。

分治的三步走

所有分治算法都遵循三个步骤：

分解（Divide）：把原问题拆成若干个规模较小的、与原问题形式相同的子问题。
解决（Conquer）：递归地解决每个子问题。如果子问题小到可以直接算出答案（比如只剩一个数），就不再递归。
合并（Combine）：把子问题的结果组合成原问题的答案。

这三个步骤就像收拾书包：

分解：先把书、作业本、文具分别拿出来。
解决：把书按大小叠好，作业本按科目放好，文具装进笔袋。
合并：最后把整理好的所有东西放回书包。

例子1：用分治法求数组最大值（入门必看）

虽然用循环求最大值更简单，但分治的框架能让你看清“分解—解决—合并”的过程。下面这段代码就是典型的分治写法：

#include <iostream>
#include <vector>
using namespace std;

// 求数组arr在区间[left, right]内的最大值
int findMax(const vector<int>& arr, int left, int right) {
    if (left == right) {                        // 只剩一个数，直接返回
        return arr[left];
    }
    int mid = left + (right - left) / 2;        // 找到中间位置
    int leftMax = findMax(arr, left, mid);      // 递归求左半部分最大值
    int rightMax = findMax(arr, mid + 1, right);// 递归求右半部分最大值
    return max(leftMax, rightMax);               // 合并：取左右中较大的
}

int main() {
    vector<int> arr = {3, 7, 2, 9, 5};          // 待求数组
    int maxVal = findMax(arr, 0, arr.size() - 1);
    cout << "最大值 = " << maxVal << endl;       // 输出 9
    return 0;
}

代码解释：

left 和 right 是当前要检查的数组区间下标。
当 left == right 时，区间里只有一个数，这个数就是最大值（递归的“终止条件”）。
否则，把区间从中间切开，分别处理左边和右边。mid = left + (right - left) / 2 可以避免 (left+right) 可能出现的溢出问题，是推荐的写法。
左右两边的最大值都算出来后，用 max() 选出更大的那个作为整个区间的最大值。

递归过程（以数组 {3,7,2,9,5} 为例）：

findMax(0,4)
   ├─ findMax(0,2)
   │    ├─ findMax(0,1)
   │    │    ├─ findMax(0,0) → 3
   │    │    └─ findMax(1,1) → 7
   │    │    → max(3,7) = 7
   │    └─ findMax(2,2) → 2
   │    → max(7,2) = 7
   └─ findMax(3,4)
        ├─ findMax(3,3) → 9
        └─ findMax(4,4) → 5
        → max(9,5) = 9
   → max(7,9) = 9

最终得到最大值9。

例子2：归并排序——分治的明星应用

归并排序是分治算法最经典的案例。它的思想很简单：要把一个无序数组排好序，先把它切成两半，分别排序，再把两个有序的子数组合并成一个整体有序的数组。

生活中的类比：老师手里有两堆按身高排好的队伍（左队和右队），现在要把它们合并成一支整体按身高排好的队伍。做法是：每次从两队的最前面各拉一个人出来，比较身高，矮的先进入新队伍，直到两队都完成。

下面是用C++实现的归并排序完整代码：

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序区间 [left, mid] 和 [mid+1, right]
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);   // 临时数组，用于存放合并结果
    int i = left, j = mid + 1, k = 0;     // i指向左半部分开头，j指向右半部分开头

    // 把两个区间中较小的元素依次放入temp
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 处理左半部分剩余的元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // 处理右半部分剩余的元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // 把临时数组中的结果拷回原数组
    for (int p = 0; p < k; ++p) {
        arr[left + p] = temp[p];
    }
}

// 归并排序：对数组arr的区间[left, right]进行排序
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) {                   // 区间为空或只有一个元素，已经有序
        return;
    }
    int mid = left + (right - left) / 2;  // 分解：找到中间位置
    mergeSort(arr, left, mid);             // 解决：递归排序左半部分
    mergeSort(arr, mid + 1, right);        // 解决：递归排序右半部分
    merge(arr, left, mid, right);          // 合并：把两个有序子数组合并
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    cout << "排序结果：";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

合并过程详解（以两个有序子数组 {27,38,43} 和 {3,9,82} 为例）：

比较 27 和 3：3小 → 放入temp
比较 27 和 9：9小 → 放入temp
比较 27 和 82：27小 → 放入temp
比较 38 和 82：38小 → 放入temp
比较 43 和 82：43小 → 放入temp
右半部分只剩 82，直接放入temp 得到 {3,9,27,38,43,82}。

例子3：最大子段和——分治也能做

你在操场上有一排同学的零花钱数额（有正有负），要选出一段连续的同学，使他们的零花钱之和最大，这就是最大子段和问题。分治可以这样处理：

分解：把数组从中点切成左右两半。
解决：递归求出左半部分的最大子段和、右半部分的最大子段和。
合并：最大子段可能还有一种情况——跨越了中点。这时需要从中点向左右两侧扩展，分别找到中点左边能取到的最大后缀和、中点右边能取到的最大前缀和，相加就是跨越中点的最大子段和。最后取三者最大值。

虽然这个问题也有更快的动态规划解法，但分治思路同样清晰，且能延伸到“平面最近点对”等更复杂的题目。

新手常犯的四个错误

忘记写递归终止条件
如果没有 if (left == right) return ...，递归会一直分下去，直到数组越界或栈溢出。哪怕只有一层也要检查。
切分点mid计算溢出
老式写法 (left + right) / 2 当 left 和 right 都很大时可能整数溢出。用 left + (right - left) / 2 更安全。
合并时索引搞混乱
比如归并排序中，temp 数组的下标和原数组的对应关系容易写错。建议用临时数组从0开始存，拷回时用 arr[left + p] = temp[p]。
假设子问题一定能合并
有些分治问题（比如快速排序）不需要显式合并，但必须保证子问题的解能组合成原问题的解。如果合并方法不对，结果就是错的。

完整可运行示例（归并排序）

上面已经给出了归并排序的完整代码。你可以直接复制到编译器里运行，看看数组 {38,27,43,3,9,82,10} 排序后的结果。如果想测试更多数据，可以把 arr 替换成自己喜欢的数字。

分治算法——大问题拆成小问题