用分治法求最大子项

/**
 * 分治法求最大子数组
 *
 * @author -lw
 * @date -2018/8/15
 * @note -
 * ---------------------------------------------------------------------------------------------------------------------
 * @modified -
 * @date -
 * @note -
 */
public class Main {
    /**
     * 入口
     *
     * @param args 参数
     */
    public static void main(String[] args) {
        double[] array = {-0, -20, 9, -10, -7, -6, 7, 5, 10, -8};
        MaxItem maxItem = findMaxiMumSubArray(array, 0, array.length - 1);
        System.out.println(maxItem.toString());
    }

    /**
     * 获取没有交叉的数组的数据的最大数组项
     *
     * @param array 数组
     * @param low   左边位置
     * @param high  右边位置
     * @return 结果
     */
    private static MaxItem findMaxiMumSubArray(double[] array, int low, int high) {
        MaxItem result = new MaxItem();
        if (low == high) {
            result.start = low;
            result.end = high;
            result.sum = array[low];
        } else {
            int middle = (low + high) / 2;
            //数组中间位置的左边的最大子项
            MaxItem resultLeft = findMaxiMumSubArray(array, low, middle);
            //数组中间位置的右边的最大子项
            MaxItem resultRight = findMaxiMumSubArray(array, middle + 1, high);
            //中间位置在数组里面的数组的最大子项
            MaxItem resultMiddle = findMaxCrossingSubarray(array, low, middle, high);
            if (resultLeft.sum >= resultRight.sum && resultLeft.sum >= resultMiddle.sum) {
                return resultLeft;
            } else if (resultRight.sum >= resultLeft.sum && resultRight.sum >= resultMiddle.sum) {
                return resultRight;
            } else {
                return resultMiddle;
            }
        }
        return result;
    }

    /**
     * 获取交叉的数组的数据的最大数组项
     *
     * @param array  数组
     * @param low    左边位置
     * @param middle 中间位置
     * @param high   右边位置
     * @return 结果
     */
    private static MaxItem findMaxCrossingSubarray(double[] array, int low, int middle, int high) {
        double leftSum = 0;
        double sum = 0;
        int maxLeft = Integer.MAX_VALUE;
        //注意这里是从middle位置向左做加法（因为最后要将中点左右两边的最大子项加起来）
        for (int i = middle; i >= low; i--) {
            sum = sum + array[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        double rightSum = 0;
        sum = 0;
        int maxRight = Integer.MAX_VALUE;
        //注意这里是从middle位置向右做加法（因为最后要将中点左右两边的最大子项加起来）
        for (int j = middle + 1; j <= high; j++) {
            sum = sum + array[j];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }
        MaxItem maxItem = new MaxItem();
        maxItem.start = maxLeft;
        maxItem.end = maxRight;
        maxItem.sum = leftSum + rightSum;
        return maxItem;
    }

    /**
     * 用于存储最大项的数据
     */
    private static class MaxItem {
        /** 开始的位置 */
        public int start;
        /** 结束的位置 */
        public int end;
        /** 最大项的数据的和 */
        public double sum;

        @Override
        public String toString() {
            return "MaxItem{" + "start=" + start + ", end=" + end + ", sum=" + sum + '}';
        }
    }


}

算法导论中的伪代码转换而来的Java语言实现的求最大子项的实现