最大和出现的情况：数组中的左边，右边和跨中点
已知股票最近几天的浮动，需要在低价买进高价卖出以获取最大利益。
需要注意的地方：
一. 跨中点方法只会计算mid参数左右两边的最大和（也是归并的时候都会执行并返回最大和， 本来当左边或者右边是负数的时候，跨中点方法就可以返回左边或者右边的值）
二. find_Max_Array方法的作用 可以当做划分数组左右两边
划分之后左边和右边返回的都是左边和右边和最大的解 ，但是当这两个都是正的时候，跨中点方法会把2个值加起来。
可能会有的疑问：
1. 为什么左右数组没有和跨越中点一样（做累加操作）却能返回区间的和
0-15对应的元素 18, 20, -7, 12, -23, -3, -25, 20, -3, -16, 13, -5, -22, 15, -4, 7
因为程序是从左往右 先算左边再算右边进行的
比如一种情况， （0，0）和最大是a0 （1，1）是a1
这样的话没有跨中点的和大（需要注意的是递归最后都会把规模切割成一份一份的），所以返回left数组 就会是（0,1,38）
然后这个结果会被上层调用（0,3）
（2,2）（3,3）
然后（0,3）的时候 左边数组是（0,1,38）
右边是（2,3,5）
这样还是没有跨中点的大，所以返回（0，3,43）
如果右边是负数 就会返回的（0,0,0）
然后还会调用跨中点的方法
主要就是这个跨中点的方法
2. 如果是返回左边的数组 右边数组和最大也是负数
这样和左边合并的时候还是会在调用中点方法的时候（右边是0）然后和左边相加
返回左边的和
@Test
public void test(){
int[] a = new int[]{18, 20, -7, 12, -23, -3, -25, 20, -3, -16, 13, -5, -22, 15, -4, 7};
int[] find_Max_Array = find_Max_Array(a, 0, 15);
System.out.println(find_Max_Array(a, 0, 15)[2]);
}
int[] a = {};//最大数组
public int[] find_Max_Cross_Subarray(int[] a, int low, int mid, int hight){
//不会递归 就分左右数组 left_sum 左的最大和 right_sum 右边的最大和 sum 总和
int[] cross_array = new int[3];//存储左边界，右边界，最大和
int left_sum = 0;
int right_sum = 0;
int max_left = 0;
int max_right = 0;
int sum1 = 0;
int sum2 = 0;
//left
for (int i = mid; i >= low; i--) {
sum1 = sum1 + a[i];
if(sum1 > left_sum){
left_sum = sum1;
max_left = i;
}
//出现一次sum<left_sum 就break 是错误的 因为值可能变小后变大
}
//right
for (int i = mid + 1; i <= hight; i++) {
sum2 = sum2 + a[i];
if(sum2 > right_sum){
right_sum = sum2;
max_right = i;
}
}
//cross_array = {max_left, max_right, sum};只能初始化时候使用这种方法
cross_array[0] = max_left;
cross_array[1] = max_right;
cross_array[2] = right_sum + left_sum;
return cross_array;
}
public int[] find_Max_Array(int[] a, int low, int hight){
int[] array = new int[3];//存储左边界，右边界，最大和
if(low >= hight ){
array[0] = low;
array[1] = hight;
array[2] = a[low];
return array;
}
else{
int mid = (low + hight)/2;
int[] left_Array = find_Max_Array(a, low, mid);
int[] right_Array = find_Max_Array(a, mid + 1, hight);
int[] cross_array = find_Max_Cross_Subarray(a, low, mid, hight);
if(left_Array[2] >= right_Array[2] && left_Array[2] >= cross_array[2]){
return left_Array;
}else if(left_Array[2] < right_Array[2] && right_Array[2] >= cross_array[2]){
return right_Array;
}else{
//中间的
return cross_array;
}
}
}
截图
