leetcode-53. 最大子序和

题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

53. 最大子序和

分析
求子序和，最一般的方法（暴力法）便是求出所有子区间的和，再求出这些子区间和的最大值即可，但这样肯定效率很低，用分治法便可解决这一问题。首先我们得明白为什么可以用分治法。
对于这个问题，我们可以考虑进行分割：

相应的全左边/全右边可以继续分割为全左边、全右边以及中间，最后再将这些分割后求出的值进行汇总即可，这恰好符合分治法分而治之的思想，所以可以使用分治法。
分支法一般采用递归处理，在此题里面，对于全左边/全右边的情形，就一直只求相应的全左边/全右边即可，关键是中间的情形。对于中间的情形，我们很容易看出来，若最大子序和在中间的话，那么其一定包含中间那个数前面的一位和中间那位数后面的一位（注意这里是考虑一般情况下），并且其一定是包含中间那位数前面一位数的最大全左子序和与包含中间那位数的后一位数的最大全右子序和之和，如下图所示

代码

public static int maxSum(int[] nums, int left, int right) {

        //判断边界条件 恰好只有一个元素
        if (left == right) {
            return nums[left];
        }

        int mid = (left + right) / 2;
        //左边最大子序和
        int leftSumMax = maxSum(nums, left, mid);
        //右边最大子序和
        int rightSumMax = maxSum(nums, mid + 1, right);

        int leftMax = Integer.MIN_VALUE;
        //在左序列中包含左边子序列最后一个元素的最大子序和
        int leftSum = 0;
        for (int i = mid; i >= left; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftSum, leftMax);
        }

        int rightMax = Integer.MIN_VALUE;
        //在右序列中包含右边子序列第一个一个元素的最大子序和
        int rightSum = 0;
        for (int i = mid + 1; i <= right; i++) {
            rightSum+=nums[i];
            rightMax=Math.max(rightSum,rightMax);
        }

        //中间子序列最大和
        int midSumMax=leftMax+rightMax;

        //返回左边、中间以及右边子序和最大值
        return Math.max(Math.max(leftSumMax,rightSumMax),midSumMax);
    }

    public static int maxSubArray(int[] nums) {

        return maxSum(nums,0,nums.length-1);

    }

2020.03.30