c++ - 如何解决这个寻找最大值和最小值的递归(分而治之)过程？

Question

为了在递归和分治法中找到最大值和最小值，我使用伪代码进行编码。但是这段代码有一个问题，我找不到maximum & minimum。 maximum & minimum 的结果在这里不正确。

#include <bits/stdc++.h>
using namespace std;

int num[50000], max1 = 0, min1 = 0, max2 = 0, min2 = 0;

void maxmin(int i, int j, int &max1, int &min2)
{
    if(i == j)
        max1 = min1 = num[i];
    else if(i == j - 1)
        {
            if(num[i] < num[j])
                {
                    max1 = num[j];
                    min1 = num[i];
                }
            else
                {
                    max1 = num[i];
                    min1 = num[j];
                }
        }
    else
    {
        int mid = (i + j) / 2;
        maxmin(i, mid, max1, min1);
        maxmin(mid+1, j, max2, min2);
        if(max1 < max2)
            max1 = max2;
        if(min1 > min2)
            min1 = min2;

    }
}

main()
{
    int n, i, minValue, maxValue;
    cout<<"No. of Data: ";
    cin>>n;
    cout<<"\nRange(min, max): ";
    cin>>minValue>>maxValue;
    for(i=0; i<n; i++)
    {
        num[i] = minValue+(rand()%(int)(maxValue-minValue+1));
    }
    maxmin(0, n-1, max1, min1);
    cout<<"\nMax: "<<max1<<"\tMin: "<<min1<<endl;
}

这个伪代码/代码有什么问题？？

Answer 1

在 maxmin(0, n-1, max1, min1); 中，您是否希望通过引用传递 max1 和 max2 ？如果是这样，您需要将函数签名修改为:

void maxmin(int i, int j, int & max1, int & min2)