分治法

分治法的思路是这样的，其实也是分类讨论。

连续子序列的最大和主要由这三部分子区间里元素的最大和得到：

    第 1 部分：子区间 [left, mid]；

    第 2 部分：子区间 [mid + 1, right]；

    第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。

对这三个部分求最大值即可。

说明：考虑第 3 部分跨越两个区间的连续子数组的时候，由于 nums[mid] 与 nums[mid + 1] 一定会被选取，可以从中间向两边扩散，扩散到底 选出最大值，具体请见。

public class Solution {

    public int maxSubArray(int[] nums) {

        int len = nums.length;

        if (len == 0) {

            return 0;

        }

        return maxSubArraySum(nums, 0, len - 1);

    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {

        // 一定会包含 nums[mid] 这个元素

        int sum = 0;

        int leftSum = Integer.MIN_VALUE;

        // 左半边包含 nums[mid] 元素，最多可以到什么地方

        // 走到最边界，看看最值是什么

        // 计算以 mid 结尾的最大的子数组的和

        for (int i = mid; i >= left; i--) {

            sum += nums[i];

            if (sum > leftSum) {

                leftSum = sum;

            }

        }

        sum = 0;

        int rightSum = Integer.MIN_VALUE;

        // 右半边不包含 nums[mid] 元素，最多可以到什么地方

        // 计算以 mid+1 开始的最大的子数组的和

        for (int i = mid + 1; i <= right; i++) {

            sum += nums[i];

            if (sum > rightSum) {

                rightSum = sum;

            }

        }

        return leftSum + rightSum;

    }

    private int maxSubArraySum(int[] nums, int left, int right) {

        if (left == right) {

            return nums[left];

        }

        int mid = (left + right) >>> 1;

        return max3(maxSubArraySum(nums, left, mid),

                maxSubArraySum(nums, mid + 1, right),

                maxCrossingSum(nums, left, mid, right));

    }

    private int max3(int num1, int num2, int num3) {

        return Math.max(num1, Math.max(num2, num3));

    }

}