算法 之 分治 - 求解最大值和最小值

分治算法可以用于求解一个数组中的最大值和最小值。具体的做法是将数组分成两个部分，分别求解左半部分和右半部分的最大值和最小值，然后比较左右两部分的最大值和最小值，得出整个数组的最大值和最小值。

具体实现时，可以使用递归的方式，将数组不断地二分，直到只剩下一个元素，此时最大值和最小值都是它本身。然后将左半部分和右半部分的最大值和最小值比较，得出整个数组的最大值和最小值。

下面是一个示例代码：

#include <iostream>
using namespace std;

struct Result {
    int max_val;
    int min_val;
};

Result max_min(int arr[], int left, int right) {
    Result res;

    if (left == right) {
        res.max_val = arr[left];
        res.min_val = arr[left];
    } else if (left + 1 == right) {
        if (arr[left] > arr[right]) {
            res.max_val = arr[left];
            res.min_val = arr[right];
        } else {
            res.max_val = arr[right];
            res.min_val = arr[left];
        }
    } else {
        int mid = (left + right) / 2;
        Result left_res = max_min(arr, left, mid);
        Result right_res = max_min(arr, mid + 1, right);

        if (left_res.max_val > right_res.max_val) {
            res.max_val = left_res.max_val;
        } else {
            res.max_val = right_res.max_val;
        }

        if (left_res.min_val < right_res.min_val) {
            res.min_val = left_res.min_val;
        } else {
            res.min_val = right_res.min_val;
        }
    }

    return res;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    Result res = max_min(arr, 0, n - 1);

    cout << "Max value: " << res.max_val << endl;
    cout << "Min value: " << res.min_val << endl;

    return 0;
}

在这个示例代码中，我们定义了一个名为 `Result` 的结构体，用来保存最大值和最小值。`max_min` 函数接收一个数组、数组的左右下标，返回一个 `Result` 结构体。

在 `max_min` 函数的实现中，我们首先判断数组的长度，如果长度为 1，则最大值和最小值都是该元素本身；如果长度为 2，则比较两个元素的大小，得出最大值和最小值；否则，将数组二分成左右两部分，分别递归求解左右两部分的最大值和最小值，并将左右两部分的最大值和最小值进行比较，得出整个数组的最大值和最小值。

在主函数中，我们定义了一个示例数组，然后调用 `max_min` 函数求解数组的最大值和最小值，并输出结果。