当前位置：首页 > news >正文

分治算法

news 2026/7/12 19:45:37

分治算法 (Divide and Conquer)

像“分家再合并”一样，把一个大问题拆成几个规模更小、相互独立的同类小问题。小问题各自解决后，再把它们的结果合并起来，最终得到大问题的答案。

经典问题推演：归并排序

分解：将包含 n 个元素的数组从中间劈开，分为左右两个 n/2 的子数组。
求解：递归地对左右两个子数组进行归并排序。当子数组只剩 1 个元素时，触发递归出口，天然有序。
合并：使用双指针，依次比较左右两个有序子数组的头部，将较小的元素放入辅助数组，最终合并成一个完整的有序数组。

最大子数组和问题 (Maximum Subarray Problem)

问题描述：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：输入 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，输出 6（因为连续子数组 [4, -1, 2, 1] 的和最大，为 6）。

为什么用分治法？

如果用暴力法，需要双重循环，时间复杂度是 \(O(n^2)\)O。而用分治法，我们可以将时间复杂度降到 \(O(nlign)\)。

核心思想：跨越中点的“三种情况”
我们将数组从中间一分为二，那么“最大子数组”只可能出现在以下三种情况中：
完全在左半边：不跨越中点。
完全在右半边：不跨越中点。
跨越中点：一部分在左半边，一部分在右半边。

核心代码

#include <stdio.h>// 辅助函数：求两个数中的最大值
int max(int a, int b) { return a > b ? a : b; }// 处理跨越中点的最大子数组和
int maxCrossingSum(int arr[], int left, int mid, int right) {// 1. 从 mid 向左扫描，求包含 arr[mid] 的左半边最大和int leftSum = -999999, sum = 0;for (int i = mid; i >= left; i--) {sum += arr[i];if (sum > leftSum) leftSum = sum;}// 2. 从 mid+1 向右扫描，求包含 arr[mid+1] 的右半边最大和int rightSum = -999999; sum = 0;for (int i = mid + 1; i <= right; i++) {sum += arr[i];if (sum > rightSum) rightSum = sum;}// 3. 左右两部分相加，即为跨越中点的最大和return leftSum + rightSum;
}// 分治法主函数
int maxSubArray(int arr[], int left, int right) {// 1. 递归出口：区间只有一个元素时，最大和就是它自己if (left == right) return arr[left];// 2. 分解（Divide）：找到中点int mid = left + (right - left) / 2;// 3. 求解（Conquer）：分别求左半边和右半边的最大子数组和int leftMax = maxSubArray(arr, left, mid);int rightMax = maxSubArray(arr, mid + 1, right);// 4. 求解跨越中点的最大子数组和int crossMax = maxCrossingSum(arr, left, mid, right);// 5. 合并（Combine）：三者取最大值return max(max(leftMax, rightMax), crossMax);
}int main() {int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int n = sizeof(arr) / sizeof(arr[0]);printf("最大子数组和为：%d\n", maxSubArray(arr, 0, n - 1));return 0;
}

示例推演

以数组 [-2, 1, -3, 4, -1] 为例（下标 0 到 4）：

第 1 层分解
目标：将问题一分为二。
中点 mid = 2（元素 -3）。
原问题被拆分为：
左子问题：[-2, 1, -3] (下标 0~2)
右子问题：[4, -1] (下标 3~4)
跨越问题：必须包含 -3 和 4

第 2 层分解（处理左子问题 [-2, 1, -3]）
中点 mid = 1（元素 1）。
左左：[-2] -> 递归到底，返回 -2。
左右：[1, -3] -> 继续拆分...（最终求得最大为 1）。
跨越：从 1 往左找最大和（1），从 -3 往右找最大和（-3），跨越和为 -2。
左子问题合并结果：max(-2, 1, -2) = 1。
第 2 层分解（处理右子问题 [4, -1]）
中点 mid = 3（元素 4）。
右左：[4] -> 返回 4。
右右：[-1] -> 返回 -1。
跨越：4 + (-1) = 3。
右子问题合并结果：max(4, -1, 3) = 4。
第 1 层合并（处理跨越中点的问题）
目标：计算必须包含 -3 和 4 的最大和。
从 -3 向左扫描：-3，然后 -3 + 1 = -2，然后 -2 + (-2) = -4。向左最大和为 -2（只取 1 和 -3 不如只取 1，但这里必须包含 -3，所以向左最多是 1 + (-3) = -2）。注：实际代码中向左扫描包含mid，最大值为 -2。
从 4 向右扫描：4，然后 4 + (-1) = 3。向右最大和为 4。
跨越中点的最大和：-2 + 4 = 2。