完全理解递归与分治：3种方法求数组最大值为例子
package myLeetcode.divide_conquer;
/**
* 方法一：
* 递推式：
* 参数： left,right;
* 思路：当前层最大值=max（max左，max右）
* 外层函数:（入栈）
* 1、分的终点：最后两个结点，返回其最大值
* 2、分的函数体，mid=(left + right )/2 ,并分别求其左右两边最小值
* 3、递推式：[left:,mid] 和[mid+1,right]
*
* 内层函数：
* 出栈：把左右两边的结果求最大值
方法二：
递推是
max=max(method(m-1),array[m]);
终结点是：
当m=1,
出栈，返回当前函数的结果即可
方法三：
传入的参数当前的max，如果当前值array[m]比原来的max更大就更新
终结点:m到达0
出栈：返回方法结果，【终点掌握，传参来接收最大值，用以此来返回】
*
*/
public class MaxTestInD_C {
public static void main(String[] args) {
int[] array={2,6,5,55,3,0,99,8,9,-1,1};
(max(array,0,array.length-1));
(max2(array,array.length-1));
(max3(array,array.length-1,array[array.length-1]));
}
//分治法求数组最大值;返回的是两个索引的最大值
public static int max(int[] array, int left, int right) {
if (left + 1 >= right) {
return (array[left], array[right]);
}
int mid = (left + right) / 2;
int leftMax = max(array, left, mid);
int rightMax = max(array, mid + 1, right);
return (leftMax, rightMax);
}
//递归法，只需要处理最后的一步就好了：缺点需要多次调用max
public static int max2(int[] array,int m){
if (m ==1){
int maxFinal= (array[0],array[1]);
return maxFinal;
}
int maxFinal=(max2(array,m-1),array[m]);
return maxFinal;
}
//分治：
//用maxNum2来保存最大的值，如果有更大的就更新，
// 每次返回的是array[maxIndex] > maxNum2
public static int max3(int[] array ,int maxIndex,int maxNum2){
if ( maxIndex == 0){
return maxNum2;
}
if (array[maxIndex] > maxNum2){
maxNum2 =array[maxIndex];
}
int maxFinal= max3(array,maxIndex-1,maxNum2);
return maxFinal;//出栈时候要返回的是结果
}
}