C++分治法求最大最小值

分治法是一种递归的思想，将问题分成若干个子问题，解决子问题后合并得到原问题的解。对于求最大最小值问题，也可以使用分治法来解决。

具体思路如下：

1. 将序列分成两个子序列。

2. 对两个子序列分别递归求解最大最小值。

3. 将两个子序列的最大最小值合并，得到原序列的最大最小值。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>

struct result {
    int max; // 最大值
    int min; // 最小值
};

struct result find_max_min(int* arr, int left, int right) {
    struct result res, left_res, right_res;
    int mid;

    if (left == right) { // 数组只有一个元素
        res.max = arr[left];
        res.min = arr[left];
        return res;
    }

    if (left + 1 == right) { // 数组有两个元素
        if (arr[left] > arr[right]) {
            res.max = arr[left];
            res.min = arr[right];
        } else {
            res.max = arr[right];
            res.min = arr[left];
        }
        return res;
    }

    // 数组有三个以上的元素
    mid = left + (right - left) / 2;
    left_res = find_max_min(arr, left, mid);
    right_res = find_max_min(arr, mid + 1, right);

    // 合并两个子序列的最大最小值
    if (left_res.max > right_res.max) {
        res.max = left_res.max;
    } else {
        res.max = right_res.max;
    }
    if (left_res.min < right_res.min) {
        res.min = left_res.min;
    } else {
        res.min = right_res.min;
    }

    return res;
}

int main() {
    int arr[] = { 3, 7, 1, 4, 2, 8, 5, 9, 6 };
    int len = sizeof(arr) / sizeof(arr[0]);
    struct result res = find_max_min(arr, 0, len - 1);
    printf("Max: %d, Min: %d\n", res.max, res.min);
    return 0;
}

运行结果：

Max: 9, Min: 1