LeetCode Maximum Product Subarray：最大乘積子陣列

LeetCode 152. 最大乘積子陣列

題目描述

給定整數陣列 A，找出連續子陣列的最大乘積。
範例：[2,3,-2,4] → 最大乘積 6 (子陣列 [2,3])。

核心難點

負數乘負數變正數，故需同時追蹤「以當前位置結尾的最大乘積」與「最小乘積」。

動態規劃最優解 (O(N) 時間, O(1) 空間)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxProd = nums[0], minProd = nums[0], ans = nums[0];
        for (size_t i = 1; i < nums.size(); ++i) {
            int x = nums[i];
            if (x < 0) swap(maxProd, minProd);  // 負數翻轉最大/最小
            maxProd = max(x, maxProd * x);
            minProd = min(x, minProd * x);
            ans = max(ans, maxProd);
        }
        return ans;
    }
};

狀態轉移邏輯

• maxProd：以 i 結尾的最大乘積
• minProd：以 i 結尾的最小乘積（可能為負，遇負數翻轉成大）
• 遇 0 時自動重置（max(0, ...) 效果）

原作者嘗試的複雜做法 (僅供參考)

原文嘗試以 0 為分界分段，段內乘積為正直接取全段，為負則從兩端嘗試除以前綴/後綴。雖然邏輯正確，但程式碼冗長、易出錯，不如上述 DP 簡潔。

關鍵測試案例

[2,3,-2,4]        → 6
[-2,0,-1]         → 0
[-2,3,-4]         → 24
[0,2]             → 2
[-2]              → -2

複雜度

• 時間：O(N)，單次遍歷
• 空間：O(1)，常數變數