最大子数组-分治策略

最大和出现的情况：数组中的左边，右边和跨中点

已知股票最近几天的浮动，需要在低价买进高价卖出以获取最大利益。

需要注意的地方：

一. 跨中点方法只会计算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;
            }
            
        }
        
    }

截图