【分治】最大值和最小值

问题描述：

给定一个大小为 $n$ 的数组 $a$，请设计一个时间复杂度为 $O(n)$ 的算法，找出其中的最大值和最小值。

思路分析：

这道题可以使用分治法来解决，将数组分成两部分，分别求出左半部分的最大值和最小值以及右半部分的最大值和最小值，然后比较得出整个数组的最大值和最小值。

具体实现如下：

C++ 代码：

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> max_min(vector<int>& a, int l, int r) {
    if (l == r) {
        return { a[l], a[l] };
    }
    int mid = (l + r) / 2;
    auto left = max_min(a, l, mid);
    auto right = max_min(a, mid + 1, r);
    return { max(left.first, right.first), min(left.second, right.second) };
}

int main() {
    vector<int> a = { 1, 3, 5, 2, 4 };
    auto res = max_min(a, 0, a.size() - 1);
    cout << "max: " << res.first << ", min: " << res.second << endl;
    return 0;
}

Python 代码：

def max_min(a, l, r):
    if l == r:
        return a[l], a[l]
    mid = (l + r) // 2
    left = max_min(a, l, mid)
    right = max_min(a, mid + 1, r)
    return max(left[0], right[0]), min(left[1], right[1])

a = [1, 3, 5, 2, 4]
res = max_min(a, 0, len(a) - 1)
print("max:", res[0], ", min:", res[1])

时间复杂度：$O(n)$。