分治法求数组元素最大最小值

分治法（Divide and Conquer）是一种常见的算法设计策略，特别适用于处理具有递归结构的问题，比如查找数组中的最大值或最小值。这种方法将复杂问题分解为规模较小但相同的子问题，然后分别求解这些子问题，最后将结果合并得到原问题的解。

对于寻找数组的最大值和最小值，我们可以使用分治法的两个步骤：

1. 分解（Divide）：
- 如果数组只有一个元素，那么它的最大值和最小值就是该元素本身。
- 如果数组有多个元素（至少两个），则可以选择第一个元素作为初始的“最大”和“最小”，然后取剩余元素的子数组再进行相同的操作。

2. 解决（Conquer）：
- 对于子数组，重复上述过程，找出子数组的最大值（max_subarray）和最小值（min_subarray）。

3. 合并（Combine）：
- 最后，将整个数组的第一个元素（初始化的最大/最小值）和子数组的最大/最小值相比较，更新全局的最大值和最小值。

这是递归版本的一个伪代码示例：

int findMax(int arr[], int low, int high) {
    if (low == high) { // base case: single element array
        return arr[low];
    } else {
        int mid = (low + high) / 2;
        int max_left = findMax(arr, low, mid);  // left half max
        int max_right = findMax(arr, mid + 1, high);  // right half max
        return (arr[mid] > max_left) ? arr[mid] : max_left;  // combine results
    }
}

int findMin(int arr[], int low, int high) {
    // Similar to the above function, but use min instead of max
    // ...
}

要同时找到最大值和最小值，你可以调用这两个函数，每个函数返回的结果可以直接组合。