利用递归思想的分治法思路求最大最小问题c++

最大最小问题也可以使用分治法来解决。具体思路如下：

1. 将序列平均分成两部分。

2. 分别递归求解左半部分和右半部分的最大值和最小值。

3. 将左半部分的最大值和最小值，右半部分的最大值和最小值进行比较，求出整个序列的最大值和最小值。

下面是c++代码实现：

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

struct Pair
{
    int maxVal;
    int minVal;
};

Pair maxMin(int arr[], int l, int h)
{
    Pair result;
    if (l == h)
    {
        result.maxVal = arr[l];
        result.minVal = arr[l];
        return result;
    }

    if (l == h - 1)
    {
        if (arr[l] < arr[h])
        {
            result.maxVal = arr[h];
            result.minVal = arr[l];
        }
        else
        {
            result.maxVal = arr[l];
            result.minVal = arr[h];
        }
        return result;
    }

    int m = (l + h) / 2;
    Pair left = maxMin(arr, l, m);
    Pair right = maxMin(arr, m + 1, h);

    result.maxVal = max(left.maxVal, right.maxVal);
    result.minVal = min(left.minVal, right.minVal);

    return result;
}

int main()
{
    int n;
    cout << "请输入序列长度：";
    cin >> n;
    int arr[n];
    cout << "请输入序列：";
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    Pair result = maxMin(arr, 0, n - 1);
    cout << "最大值为：" << result.maxVal << endl;
    cout << "最小值为：" << result.minVal << endl;

    return 0;
}

输入样例：

请输入序列长度：8
请输入序列：-2 1 -3 4 -1 2 1 -5

输出样例：

最大值为：4
最小值为：-5