分治思想实现求连续子数组的最大和-白红宇

基本的思路是：计算中点，将数组不断细分为更小的数组。连续子数组的最大和只能在以下三种情况产生：

连续子数组的最大和在中点的左边产生

连续子数组的最大和在中点的右边产生

连续子数组的最大和跨越中点

根据上述思路，我们很容易写出如下代码：

public class MaxSubClass {    static int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};    //求最大子数组    public int getMaxSubArray(int[] array, int low, int high) {        if (low == high)            return array[low];        //第一种情况最大子数组在左边的数组产生        int mid = (low + high) / 2;        int maxLeft = getMaxSubArray(array, low, mid);        //第二种情况最大子数组在右边的数组产生        int maxRight = getMaxSubArray(array, mid + 1, high);        //第三种情况最大子数组跨越中点产生        int maxCross = getMaxCrossSubArray(array, low, mid, high);        //取三者的最大值        int max = maxLeft > maxRight ? maxLeft : maxRight;        max = maxCross > max ? maxCross : max;        return max;    }    //求跨中点的最大子数组    public int getMaxCrossSubArray(int[] array, int low, int mid, int high) {        int leftMaxSum = array[mid];        int leftSum = array[mid];        int leftIndex = mid;        for (int i = mid -1 ; i >= low; i--) {            leftSum = leftSum + array[i];            if (leftSum > leftMaxSum)                leftMaxSum = leftSum;        }        int rightMaxSum = 0;        int rightSum = 0;        int rightIndex = mid;        for (int j = mid + 1; j <= high; j++) {            rightSum = rightSum + array[j];            if (rightSum > rightMaxSum)                rightMaxSum = rightSum;        }        int max = leftMaxSum + rightMaxSum;        return max;    }    public static void main(String[] args) {        MaxSubClass mc = new MaxSubClass();        System.out.println(mc.getMaxSubArray(arr, 0, arr.length - 1));    }}复制代码