分治法的经典问题——求数列中最大最小值

前面我们已经了解了分治法的原理和使用，分治法的经典问题——大整数相乘，趁热打铁，来学习一下如何使用分治法来求数列中的最大最小值。

利用分治法来分析

伪代码

时间复杂性

代码实现

#include<cstdio> #include<cstdlib> #include<cmath> using namespace std; int* getmaxmin(int a, int b){ int* m = new int[2]; if(a < b){ m[0] = a; m[1] = b; }else{ m[0] = b; m[1] = a; } printf("getmaxmin的值：%d, %d\n", m[0], m[1]); return m; } //m[0]存放最小值，m[1]存放最大值 int* maxmin(int a[], int n1, int n2){ if((n2 - n1 + 1)== 1){ int* m = new int[2]; m[0] = -1; m[1] = a[n2]; return getmaxmin(a[n2], a[n2]); }else if((n2 - n1 + 1) == 2){ return getmaxmin(a[n1], a[n2]); }else{ int k = n1 + (n2 - n1) / 2; int* lm = maxmin(a, n1, k); int* rm = maxmin(a, k+1, n2); printf("lm得到的值：%d, %d\n", lm[0], lm[1]); if(rm[0] == -1){ printf("rm得到的值：%d\n", rm[1]); } printf("rm得到的值：%d, %d\n", rm[0], rm[1]); int* result = new int[2]; if(lm[0] < rm[0]){ result[0] = lm[0]; }else{ result[0] = rm[0]; } if(lm[1] < rm[1]){ result[1] = rm[1]; }else{ result[1] = lm[1]; } return result; } } int main(){ int a[8] = {6,10,32,8,19,20,2,14}; int* result = maxmin(a, 0, 7); printf("最大值为：%d，最小值为：%d", result[1], result[0]); }

结果如下：