JZ85 連續子數組的最大和(二)

題目

輸入一個長度為n的整型數組array，數組中的一個或連續多個整數組成一個子數組，找到一個具有最大和的連續子數組。
1.子數組是連續的，比如[1,3,5,7,9]的子數組有[1,3]，[3,5,7]等等，但是[1,3,7]不是子數組
2.如果存在多個最大和的連續子數組，那麼返回其中長度最長的，該題數據保證這個最長的只存在一個
3.該題定義的子數組的最小長度為1，不存在為空的子數組，即不存在[]是某個數組的子數組
4.返回的數組不計入空間複雜度計算

方法 動態規劃

思路

演算法實現

既然是連續子數組，如果我們拿到了當前的和，對於後面一個即將加入的元素，如果加上他這一串會變得更大，我們肯定會加上它，
如果它自己會比加上前面這一串更大，說明從它自己開始連續子數組的和可能會更大。
具體做法：
    step 1：創建動態規劃輔助數組，記錄到下標i為止的最大連續子數組和，下標為0的時候，肯定等於原數組下標為0的元素。
    step 2：準備左右區間雙指針記錄每次連續子數組的首尾，再準備兩個雙指針記錄最大和且區間最長的連續子數組的首尾。
    step 3：遍曆數組，對於每個元素用上述狀態轉移公式記錄其dp值，更新區間首尾（如果需要）。
    step 4：出現一個最大值。且區間長度更大的時候，更新記錄最長區間的雙指針。
    step 5：根據記錄的最長子數組的位置取數組。

代碼

package mid.JZ85連續子數組的最大和2;

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * @param array int整型一維數組
     * @return int整型一維數組
     */
    public int[] FindGreatestSumOfSubArray(int[] array) {
        // write code here
        if (array.length == 1) return array;
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = dp[0];
        //滑動區間
        int left = 0, right = 0;
        //記錄最長區間
        int resl = 0, resr = 0;
        for (int i = 1; i < array.length; i++) {
            right++;
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            if (dp[i - 1] + array[i] < array[i]) {
                //如果左邊加起來還沒有這個值大，那麼重新定義left為這個值
                left = right;
            }
            if (dp[i] > max || dp[i] == max && (right - left + 1) > (resr - resl + 1)) {
                max = dp[i];
                resl = left;
                resr = right;
            }
        }

        int[] res = new int[resr - resl + 1];
        for (int i = resl; i <= resr; i++) {
            res[i - resl] = array[i];
        }
        return res;
    }
}