給你一個整數(shù)數(shù)組 nums ，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。子數(shù)組 是數(shù)組中的一個連續(xù)部分。

解題思路：貪心 / 動態(tài)規(guī)劃

方法1. 貪心算法

? 本題貪心貪在哪？
——在遍歷的過程不斷計算和，如果當前和變成了負數(shù)，那么我們就應該舍棄，直接從當前元素作為起始重新計算和。
為什么可以這樣？因為不管后面的數(shù)是正數(shù)還是負數(shù)，加一個負數(shù)只會越變越??！
舍棄不會把前面計算的最大值一同扔掉嗎？不會。因為我們每次計算和，都會維護一個最大的和。

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. 動態(tài)規(guī)劃

定義dp[i]：以nums[i]結尾的連續(xù)子數(shù)組的最大和。
● 狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1], dp[i-1] + nums[i]); dp[0]=nums[0]

可以在計算dp的過程中，保存最大值；或者計算完成dp數(shù)組后再遍歷一次，取最大值。

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. 分治遞歸

我們將數(shù)組劃分成若干個子數(shù)組，每次劃分有左子樹組[left, mid]，和右子數(shù)組[mid+1, right]。

然后對以下3種情況進行討論：
(1) 左子樹組的連續(xù)子數(shù)組最大和
(2) 右子數(shù)組的連續(xù)子數(shù)組最大和
(3) 位于中間（跨左右子數(shù)組），包含[mid, mid+1]的連續(xù)子數(shù)組最大和。
?求跨左右子數(shù)組的連續(xù)子數(shù)組，只需要從中間向兩邊擴散，擴散邊界，選出最大值即可。

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); // 計算左子數(shù)組連續(xù)最大和
        int rightMax = recur(nums, mid+1, right); // 計算右子數(shù)組連續(xù)最大和

        // 計算跨左、右子數(shù)組連續(xù)最大和
        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;
    }
}