分治算法求n个元素的最大值和最小值
算法思想:
1.将n个数均分为s1和s2
2.分别求解s1和s2的最大值和最小值
s1最大值为max1,s1最小值为min1
s2最大值为max2,s2最小值为min2
3.计算min(min1,min2),max(max1,max2)
void Maxmin(int a[],int l,int r,int &x,int &y){if(l==r)///只有一个数的情况{x=a[l],y=a[l];return;}if(r-l==1)///只有两个数的情况{if(a[l]<a[r]){x=a[l],y=a[r];}else{x=a[r],y=a[l];}}else{int mid=(l+r)/2;int x1,y1,x2,y2;Maxmin(a,l,mid,x1,y1);Maxmin(a,mid+1,r,x2,y2);x=min(x1,x2);y=max(y1,y2);}}