最大子序列（maximum-subarray）问题

假设序列为A[low..high]，有mid=(low+high)/2 左半部分为A[low,mid],右半部分为A[mid+1,high]
假设所求最大序列区间为A[i,j]

• 最大子序列在左半部分 low<=i<=j<=mid
• 最大子序列在右半部分 mid<i<=j<=high
• 最大子序列跨越了左半部分和右半部分 low<=i<=mid<j<=high
  最大子序列sum值为三种情况中的最大值

import java.util.Arrays;

public class MaxSubArrayTest {
    public static void main(String[] args) {
        int []array={4,-3,5,-2,-1,2,6,-2};
       System.out.println(findMaximumSubarray(array,0,array.length-1));


    }
    public static int findMaximumSubarray(int[] array,int low ,int high){
            if(low==high){
                return array[low];
            }else {
                int mid=(low+high)/2;
                int leftSum=findMaximumSubarray(array,low,mid);
                int rightSum=findMaximumSubarray(array,mid+1,high);
                int crossSum=findMaxCrossingSubarray(array,low,mid,high);
                System.out.println(leftSum+":"+rightSum+":"+crossSum);
                //取三种情况的最大值
                return maxValue(leftSum,rightSum,crossSum);
            }
    }
    //求最大值
    public static int maxValue(int ...value){
        return  Arrays.stream(value).max().getAsInt();
    }
    //求跨越mid的最大值
    private static int findMaxCrossingSubarray(int[] array, int low, int mid, int high) {
        int leftSum=0;
        int sum=0;
        //array[low..mid]的最大子序列和
        for(int i=mid;i>=low;i--){
            sum+=array[i];
            if(sum>leftSum){
                leftSum=sum;
            }
        }
        sum=0;
        int rightSum=0;
        //array[mid+1..high]的最大子序列和
        for (int j=mid+1;j<=high;j++){
            sum+=array[j];
            if(sum>rightSum){
                rightSum=sum;
            }
        }
        return maxValue(leftSum,rightSum,leftSum+rightSum);
    }
}