最大字数组问题一种java实现，理论部分参见算法导论分治策略

public class Solution {
    private static class result{
        int left;
        int right;
        int sum;
    }
     //递归查找最大子数组
    public static result findMaxSubArray(int[]array,int low, int high) {
        if(high==low) {
            result result = new result();
            result.left = low;
            result.right = high;
            result.sum = array[low];
            return result;
        }
        else {
            int mid = low + (high-low)/2;
            result left = findMaxSubArray(array,low,mid);
            result right = findMaxSubArray(array,mid+1,high);
            result cross = findCrossMaxSubArray(array,low,mid,high);
            int max = Math.max(left.sum,Math.max(right.sum,cross.sum));
            if (left.sum==max) return left;
            else if (right.sum==max) return right;
            else return cross;
        }
    }
//查找经过中点的最大子数组
    public static result findCrossMaxSubArray(int[] array, int low, int mid, int high) {
        result result = new result();
        int sum=0;
        int maxLeft = Integer.MIN_VALUE;
        int maxRight = Integer.MIN_VALUE;
        for (int i = mid;i>=low;i--) {
            sum += array[i];
            if (sum>maxLeft) {
                maxLeft = sum;
                result.left = i;
            }
        }
        sum = 0;
        for (int i=mid+1;i<=high;i++) {
            sum +=array[i];
            if (sum>maxRight) {
                maxRight = sum;
                result.right = i;
            }
        }
        result.sum = maxLeft + maxRight;
        return result;
    }

    public static void main(String[]args) {
        int[] array = {13,-3,-25,20,//
                -3,-16,-23,18,//
                20,-7,12,-5,//
                -22,15,-4,7 };
        result result = findMaxSubArray(array,0,array.length-1);
        System.out.println("第" + result.left + "天买入,第" + result.right + "天卖出可获得最大差价：" + result.sum);
    }
}