Question

分治算法的一个小问题，求一个数组的最大最小值，算法如图，怎么实现？求指教

如果设一个maxmin函数，要返回两个值，不行，不知道要怎么实现，
小弟只会c语言跟一点java

Answer 1

//求一个数组A[i...j]的最大值和最小值，分支算法，递归实现
//2015.2.9
//dev c++
#include<stdio.h>
#include<malloc.h>

int min(int a,int b){
    return a<b? a:b;
}
int max(int a,int b){
    return a>b? a:b;
}
int* MaxMin(int a[],int i,int j)
{
     int *m=(int *)malloc(2*sizeof(int));
     if(j-i+1==1){
         m[0]=m[1]=a[i];
         return m;
     }
     if(j-i+1==2){
         if(a[i]<a[j]){
             m[0]=a[i];
             m[1]=a[j];      
         }
         else{
             m[0]=a[j];
             m[1]=a[i];
         }
         return m;
     }
     int k=(j-i+1)/2;
     int *m1 = MaxMin(a,i,k);
     int *m2 = MaxMin(a,k+1,j);
     m[0]=min(m1[0],m2[0]);
     m[1]=max(m1[1],m2[1]);
     return m;
}
int main()
{
    int a[128];
    int n;
    int i;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        int *m = MaxMin(a,0,n-1);
        printf("%d %d\n",m[0],m[1]);
    }
    return 0;
}

追问

谢谢，好像比较大的数组就不行

8
6 10 32 8 19 20 2 14
请按任意键继续. . .

七个数开始就不行了

追答

是的，你可以加两个free，释放不用的内存（malloc申请的）

Answer 2

可以用指针来实现
void MaxMin(int i1,int j1,int *m,int *M) //求i1~i2之间的最小值*m和最大值*M
用MaxMin(i,k,&m1,&M1)
和MaxMin(k+1,j,&m2,&M2)
来调用。

Answer 3

这个算法反而复杂了。这道题用分治复杂度也是O（N），线性扫描也是O(N)。如果你的确想要代码的话，请指明语言。

追问

c语言可以吗？