【连续子数组】53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

解题思路：贪心 / 动态规划

方法1. 贪心算法

⭕ 本题贪心贪在哪？
——在遍历的过程不断计算和，如果当前和变成了负数，那么我们就应该舍弃，直接从当前元素作为起始重新计算和。
为什么可以这样？因为不管后面的数是正数还是负数，加一个负数只会越变越小！
舍弃不会把前面计算的最大值一同扔掉吗？不会。因为我们每次计算和，都会维护一个最大的和。

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            if(sum < 0) sum = 0;
            sum += nums[i];
            if(max < sum) max = sum;
        }
        return max;
    }
}

方法2. 动态规划

定义dp[i]：以nums[i]结尾的连续子数组的最大和。
● 状态转移方程：dp[i] = max(dp[i-1], dp[i-1] + nums[i]); dp[0]=nums[0]

可以在计算dp的过程中，保存最大值；或者计算完成dp数组后再遍历一次，取最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        int dp[] = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for(int i=0; i<nums.length; i++){
            if(i == 0) dp[0] = nums[0];
            else{
                dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
            }
            if(max < dp[i]) max = dp[i];
        }
        return max;
    }
}

方法3. 分治递归

我们将数组划分成若干个子数组，每次划分有左子树组[left, mid]，和右子数组[mid+1, right]。

然后对以下3种情况进行讨论：
(1) 左子树组的连续子数组最大和
(2) 右子数组的连续子数组最大和
(3) 位于中间（跨左右子数组），包含[mid, mid+1]的连续子数组最大和。
 求跨左右子数组的连续子数组，只需要从中间向两边扩散，扩散边界，选出最大值即可。

class Solution {
    public int maxSubArray(int[] nums) {
        return recur(nums, 0, nums.length-1);
    }
    public int recur(int[] nums, int left, int right){
        if(left == right) return nums[left];

        int mid = left + (right - left) / 2;
        
        int leftMax = recur(nums, left, mid); // 计算左子数组连续最大和
        int rightMax = recur(nums, mid+1, right); // 计算右子数组连续最大和

        // 计算跨左、右子数组连续最大和
        int midMax = 0;
        int curMax = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=mid; i>=left; i--){
            sum += nums[i];
            if(sum > curMax) curMax = sum;
        }
        midMax += curMax;
        curMax = Integer.MIN_VALUE;
        sum = 0;
        for(int i=mid+1; i<=right; i++){
            sum += nums[i];
            if(sum > curMax) curMax = sum;
        }
        midMax += curMax;
        
        return max3(leftMax, rightMax, midMax);
    }
    public int max3(int a, int b, int c){
        a = Math.max(a, b);
        a = Math.max(a, c);
        return a;
    }
}