leetcode 52 最大值子序和 看得懂的分治

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法一 分而治之

这个解法其实动态规划有效率，但是很有意思啊。毕竟

To Iterate is Human, to Recurse, Divine.

分而治之其实就是分解大问题成子问题，再分解子问题至基本情况，最后合并子问题的解以获得原始问题解的过程。

俗话来说就是大事化小，小事化了，基本情况（base case)就是可以化了的最小事情，因为结果显而易见，比如求一个数的数组的最大子数组和。
但这个俗话模型不太完整，因为它缺少了合并子问题的解以获得原始问题的解的过程。

具体到这个问题，
我们先设定数组中索引 <= (left + right) / 2 的一半为左半边，数组中索引 > (left + right) / 2 的一半为右半边

那么最大子数组的开头和结尾（题中有说明，两者是可以重叠的）可能：

• 都在左半边中
• 都在右半边中
• 开头在左，结尾在右

对于前两种情况，我们继续划分为以上三种情况，直到不能再分的基本情况。
最后一种情况，我们由中间元素分别向左右两边拓展，分别找出左右两边以中间元素结尾（开始）的子数组最大和，然后返回两者的和。

public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1); // 递归入口 
    }
    public int helper(int[] nums, int le, int ri){
        if(le == ri) return nums[le]; // 递归的 base case 
        int mi = (le + ri) / 2; // 中间元素的索引
        int leSum = helper(nums, le, mi); // 左半边继续划分
        int riSum = helper(nums, mi + 1, ri); // 右半边继续划分
        int crossSum = crossSum(nums, le, ri, mi); // 

        return Math.max(crossSum, Math.max(leSum, riSum)); // 返回三个部分中最大值
    }
    public int crossSum(int[] nums, int le, int ri, int mi){
        if(le == ri) return nums[le]; // 递归的 base case 

        int leSubSum = Integer.MIN_VALUE;
        int curSum = 0;
        for(int i = mi; i > le - 1; i--){ // 从中间开始向左拓展，找出左边的最大和
            curSum += nums[i];
            leSubSum = Math.max(leSubSum, curSum);
        }

        int riSubSum = Integer.MIN_VALUE;
        curSum = 0;
        for(int i = mi + 1; i < ri + 1; i++){ // 从中间开始向左拓展，找出右边的最大和
            curSum += nums[i];
            riSubSum = Math.max(riSubSum, curSum);
        }

        return leSubSum + riSubSum;
    }