从小白开始刷算法 分治法篇 leetcode.53

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public int maxSubArray(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        return getMax(nums, start, end);
    }
    private int getMax(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int middle = start + (end - start) / 2;
        //递归计算左侧子数组和中最大子数组和
        int leftMax = getMax(nums, start, middle);
         //递归计算右侧子数组和中最大子数组和
        int rightMax = getMax(nums, middle + 1, end);
        //上述代码与之前169题中分治法中逻辑大体一致
        //这里开始计算跨越中间位置的最大子数组和
        int crossMax = getCrossMax(nums, start, end);
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
    private int getCrossMax(int[] nums, int start, int end) {
        int middle = start + (end - start) / 2;
        int leftSum = nums[middle];
        int leftMax = leftSum;
        for (int i = middle - 1; i >= start; i--) {
            leftSum = leftSum + nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        int rightSum = nums[middle + 1];
        int rightMax = rightSum;
        for (int i = middle + 2; i <= end; i++) {
            rightSum = rightSum + nums[i];
            rightMax = Math.max(rightMax, rightSum);
        }
        return leftMax + rightMax;
    }
}