LeetCode Maximum Product Subarray：動態規劃維護局部最大最小值

問題描述

給定整數數組，找出乘積最大的連續子數組（至少含一個數）。例如 [2,3,-2,4] 最大乘積子數組 [2,3] 乘積 6。

暴力法缺陷

枚舉所有子數組 O(n^3) 或 O(n^2)，超時。

動態規劃核心洞察

負數翻轉最大/最小值。維護兩個狀態：

• curMax：以當前元素結尾的最大乘積
• curMin：以當前元素結尾的最小乘積（可能為負，遇負翻正）

轉移方程：

curMax = max(A[i], A[i]*curMax, A[i]*curMin)
curMin = min(A[i], A[i]*curMax_old, A[i]*curMin)

優化實現

int maxProduct(int A[], int n) {
    int ans = A[0], curMax = A[0], curMin = A[0];
    for (int i=1; i

關鍵細節

使用臨時變量 t 保存舊 curMax，避免更新順序影響 curMin 計算
初始值設為首元素，正確處理單元素數組
全局最大值 ans 每步更新
時間 O(n)，空間 O(1)


示例演示
數組: [2, 3, -2, 4]
i=0: curMax=2, curMin=2, ans=2
i=1: curMax=6, curMin=3, ans=6  (2*3)
i=2: curMax=-2, curMin=-12, ans=6 (3*-2=-6, 但 max(-2, -6, -12)=-2)
i=3: curMax=4, curMin=-48, ans=6  (-2*4=-8, max(4, -8, -48)=4)
最終答案 6