力扣 – 劍指 Offer 42. 連續子數組的最大和

• 2021 年 11 月 27 日
• 筆記
• 動態規劃, 數組, 算法與題解

題目

劍指 Offer 42. 連續子數組的最大和

思路1（分析數組的規律）

• 我們可以從頭到尾逐個累加，若之前的累加和小於0，那就從丟棄之前的累加，從當前開始重新累加，同時在遍歷過程中比較記錄下最大值
  • curSum記為當前最大值，為 0，以 [-2,1,-3,4,-1,2,1,-5,4] 為例：
    1. 首先加上 -2，此時 curSum 為 -2
    2. 由於 -2 小於 0，所以丟棄，然後再加上 1，此時 curSum 為 1
    3. 再加上 -3，此時 curSum 為 -2
    4. 由於 -2 小於 0，所以再次丟掉，然後加上 4，此時 curSum 為4
    5. 然後加上 -1，此時 curSum 為 3
    6. 再加上 2，此時 curSum 為 5
    7. 再加上 1，此時 curSum 為 6
    8. 再加上 -5，此時 curSum 為 1
    9. 最後再加上最後一個 4，此時 curSum 為 5
    10. 在這每次遍歷中，我們使用一個變量 res 存儲最大值，可以找到最大值為 6

代碼

class Solution {
    public int maxSubArray(int[] nums) {

        int length = nums.length;
        // 最大總和值
        int res = Integer.MIN_VALUE;
        // 當前總和
        int curSum = 0;

        for (int i = 0; i < length; i++) {
            if (curSum < 0) {
                // 如果 i 之前總和值小於0，那就從 i 開始重新計算
                curSum = nums[i];
            } else {
                // 否則加上當前的值
                curSum += nums[i];
            }

            // 尋找最大值
            if (curSum > res) {
                res = curSum;
            }
        }

        return res;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)

思路2（動態規劃）

• 和思路一差不多動態規劃就是利用歷史記錄，避免重複計算。所以也是從頭到尾逐個累加，若之前的累加和小於0，那就從丟棄之前的累加，從當前開始重新累加，我們可以定義一個 dp 數組，dp[i] 代表的意義就是以 i 結尾的子數組的最大值。因此我們可以得出狀態轉移方程：

  \[dp[i] = \begin{cases} dp[i-1]+nums[i], & \text{if } dp[i-1]<0 \\ nums[i], & \text{if } dp[i-1]\geq0 \end{cases}
  \]

• 既然我們可以得到以 i 結尾子數組的最大值，那麼只需要從這些最大值中找到最大的一個就是結果了～

代碼

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        dp[0] = nums[0];
        int res = dp[0];

        for (int i = 1; i < length; i++) {
            dp[i] = dp[i-1] > 0 ? dp[i-1]+nums[i] : nums[i];
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

可以進一步優化：

class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        // 記錄子數組中的最大值
        int res = Integer.MIN_VALUE;
        // 記錄前一段子數組之和
        int preSum = 0;

        for (int num : nums) {
            // 意思也是判斷前一個字數組之和是否小於0
            preSum = Math.max(num, preSum + num);
            // 然後記錄最大值
            res = Math.max(res, preSum);
        }

        return res;
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)