第48章 分治算法

返回类型 divideConquer(问题参数) {
    // 基本情况：规模足够小，直接返回解
    if (问题规模足够小) {
        return 直接求解结果;
    }
    // 1. 分解：拆分出多个子问题
    子问题1, 子问题2... = 分解原问题;
    // 2. 递归求解所有子问题
    解1 = divideConquer(子问题1参数);
    解2 = divideConquer(子问题2参数);
    // 3. 合并子问题答案
    原问题解 = 合并(解1, 解2...);
    return 原问题解;
}

#include <iostream>
using namespace std;

// 合并 [left,mid] 和 [mid+1,right] 两个有序区间
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = new int[n1];
    int* R = new int[n2];
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    // 双指针合并
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    // 复制剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    delete[] L;
    delete[] R;
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);     // 左半分治
        mergeSort(arr, mid + 1, right); // 右半分治
        merge(arr, left, mid, right);   // 合并有序区间
    }
}

#include <iostream>
using namespace std;

// 划分函数，返回基准最终下标
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选最右侧为基准
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);   // 基准左侧
        quickSort(arr, pi + 1, high);  // 基准右侧
    }
}

#include <climits>
// 求跨越中点的最大和
int maxCrossingSum(int arr[], int left, int mid, int right) {
    int sum = 0, leftMax = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftMax) leftMax = sum;
    }
    sum = 0;
    int rightMax = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > rightMax) rightMax = sum;
    }
    return leftMax + rightMax;
}

int maxSubArraySum(int arr[], int left, int right) {
    // 基本情况：区间仅一个元素
    if (left == right) return arr[left];
    int mid = left + (right - left) / 2;
    int leftSum = maxSubArraySum(arr, left, mid);
    int rightSum = maxSubArraySum(arr, mid + 1, right);
    int crossSum = maxCrossingSum(arr, left, mid, right);
    // 三者取最大
    return max(max(leftSum, rightSum), crossSum);
}