6-2 分治法求解金块问题

description

老板有一袋金块（共n块，2≤n≤100），两名最优秀的雇员每人可以得到其中的一块，排名第一的得到最重的金块，排名第二的则得到袋子中最轻的金块。

输入一个正整数N（2≤N≤100）和N个整数，用分治法求出最重金块和最轻金块。

本题要求实现2个函数，分别使用分治法在数组中找出最大值、最小值。

函数接口定义：
int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);
递归函数max用分治法求出a[m]~a[n]中的最大值并返回。

递归函数min用分治法求出a[m]~a[n]中的最小值并返回。

裁判测试程序样例：
#include <stdio.h>
#define MAXN 101

int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);

int main(void)
{
int i, n;
int a[MAXN];

scanf ("%d", &n); 
if(n >= 2 && n <= MAXN-1 ){for(i = 0; i < n; i++){ scanf ("%d", &a[i]); }printf("max = %d\n", max(a, 0, n-1));printf("min = %d\n", min(a, 0, n-1));
}else{printf("Invalid Value.\n");    
}return 0;

}

/* 请在这里填写答案 */

输入样例：

6
3 9 4 9 2 4

输出样例：

max = 9
min = 2

solution

/* 请在这里填写答案 */
int max(int a[ ], int m, int n){if(m == n) return a[m];else{int mid = (m + n) / 2;int lMax = max(a, m, mid);int rMax = max(a, mid + 1, n);if(lMax > rMax) return lMax;else return rMax;}
}
int min(int a[ ], int m, int n){if(m == n) return a[m];else{int mid = (m + n) / 2;int lMin = min(a, m, mid);int rMin = min(a, mid + 1, n);if(lMin < rMin) return lMin;else return rMin;}
}