题解 | 求最大最小数 分治法

// 方法二：递归，分治法，二分法
#include <iostream>
using namespace std;

// 引用改变原值
void maxmin(int i, int j, int& fmax, int& fmin, int data[]) {
    int mid, lmax, lmin, rmax, rmin;
    if (i == j) { // 最小的相同类型问题
        fmax = data[i];
        fmin = data[i];
    } else if (i == j - 1) { // 相邻/相差0位/只有两位
        if (data[i] > data[j]) {
            fmax = data[i];
            fmin = data[j];
        }
        if (data[i] < data[j]) {
            fmax = data[j];
            fmin = data[i];
        }
    } else {
        mid = (i + j) / 2;
        maxmin(i, mid, lmax, lmin, data);
        maxmin(mid + 1, j, rmax, rmin, data);
        if (rmax > lmax) {
            fmax = rmax;
        } else {
            fmax = lmax;
        }
        if (rmin < lmin) {
            fmin = rmin;
        } else {
            fmin = lmin;
        }
    }
}

int main() {
    int n, fmax, fmin, data[10000];
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> data[i];
        }
        maxmin(0, n - 1, fmax, fmin, data);
        cout << fmax << " " << fmin << endl;;
    }
}