主題: 學習筆記

LeetCode 152：最大乘積子陣列，為什麼最大值和最小值都要留下

記錄我的 Maximum Product Subarray 解題過程，從正負號分支改成 O(n) 的最大與最小雙狀態，並用反例、不變量及暴力比對說明正確性。

這題是 Maximum Subarray 的變形，但加法換成乘法後，原本只保存最大值的做法不夠了。負數會把大小關係反轉：前一輪最小的負值，乘上另一個負數，可能成為這一輪最大的正值。

我一開始用 endHereAbs 和 isEndHereNegative 分別追蹤絕對值與正負號。分支愈寫愈多，狀態代表的意義也開始混在一起。卡住後，我依 AI 提示改成直接保存「最大乘積」與「最小乘積」。最後的程式很短，但真正需要理解的是這兩個狀態為什麼足夠。

題目

LeetCode 152：Maximum Product Subarray 給定整數陣列，要求找出非空連續子陣列的最大乘積，並回傳該乘積。

例如 [2,3,-2,4] 的答案是 6，來自 [2,3]。[-2,0,-1] 的答案是 0，不能把不相鄰的 -2 與 -1 相乘。輸入長度介於 1 到 20000，元素介於 -10 到 10；題目保證任一子陣列乘積與答案都在 32 位元有號整數範圍內。

我的第一版：自己管理正負號

以下是我卡住時的版本。為了與最終版本放在同一篇文章，函式改名為 maxProductFirstAttempt。

function maxProductFirstAttempt(nums: number[]): number {
    let endHere = nums[0];
    let endHereAbs = nums[0];
    let isEndHereNegative = nums[0] < 0;
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === 0) {
            endHere = 0;
            endHereAbs = 0;
            isEndHereNegative = false;
        } else if (isEndHereNegative) {
            if (nums[i] < 0) {
                endHere = Math.abs(endHereAbs * nums[i]);
                if (Math.abs(nums[i] * endHereAbs) > 0 - nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            } else {
                endHere = nums[i];
                if (Math.abs(nums[i] * endHereAbs) > nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            }
            isEndHereNegative = endHere < 0;
        } else {
            if (nums[i] > 0) {
                endHere = Math.max(endHere * nums[i], nums[i]);
                if (Math.abs(nums[i] * endHereAbs) > nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            } else {
                endHere = nums[i];
                if (Math.abs(nums[i] * endHereAbs) > 0 - nums[i]) {
                    endHereAbs = nums[i] * endHereAbs;
                } else {
                    endHereAbs = nums[i];
                }
            }
            isEndHereNegative = endHere < 0;
        }

        best = Math.max(endHere, best, endHereAbs);
    }

    return best;
}

這版已經發現負數是難點，也知道需要保留一個可能在之後翻正的狀態。不過 endHereAbs 有時保存原始負值，有時保存乘積，有時又拿絕對值比較；isEndHereNegative 則只根據 endHere 更新。三個變數沒有穩定的不變量，分支很難驗證。

反例是 [-1,-1,-2]。正確答案為 2，來自 [-1,-2]，第一版卻回傳 1。即使調整其中一個 >，仍然只是在修特定路徑；真正要修的是狀態的定義。

我的第二版：保存最大與最小乘積

這是我依提示完成並提交的版本：

function maxProduct(nums: number[]): number {
    let maxEndingHere = nums[0];
    let minEndingHere = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        const previousMax = maxEndingHere;
        const previousMin = minEndingHere;

        maxEndingHere = Math.max(previousMin * num, previousMax * num, num);
        minEndingHere = Math.min(previousMin * num, previousMax * num, num);
        best = Math.max(best, maxEndingHere);
    }

    return best;
}

這版不判斷目前數字是正數、負數或零，而是每輪都比較相同的三個候選：

1. 只取目前的 num，從目前位置重新開始。
2. 把 num 接在上一輪最大乘積後面。
3. 把 num 接在上一輪最小乘積後面。

當 num 是正數，上一輪最大值通常產生新最大值；當 num 是負數，上一輪最小值可能翻成新最大值。三個候選一起比較，就不必替符號撰寫不同分支。

狀態不變量

處理完索引 i 後：

• maxEndingHere 是所有「剛好在 i 結束」的非空連續子陣列中，最大的乘積。
• minEndingHere 是相同候選中最小的乘積。
• best 是從索引 0 到 i 之間出現過的最大乘積。

任何在 i 結束的連續子陣列，只可能是 [nums[i]]，或是某個在 i - 1 結束的連續子陣列再乘上 nums[i]。固定乘上一個數字後，最大值只可能來自上一輪的最大或最小端點；中間值不會超過這兩個極端。因此保存 previousMax 與 previousMin 就涵蓋了所有候選。

必須先複製上一輪的兩個值。若先更新 maxEndingHere，再使用更新後的值計算 minEndingHere，第二個狀態就會混入本輪結果，相當於重複使用目前元素。

跟著 [2,-5,-2,-4,3] 走一次

索引 2 的 -2 乘上前一輪最小值 -10，得到新的最大值 20。索引 4 的答案則來自重新整理過的局部最大值 8，再乘上 3 得到 24。

零也會自然重設狀態。三個候選都是 0 或含有 0 的乘積，因此最大與最小都變成 0；下一個非零數字仍可透過候選 num 重新開始，不需要額外分支。

暴力解與瓶頸

最直接的方式是枚舉每個起點，再一路向右累乘，總共有 O(n²) 個連續子陣列。它適合當小型測試的參考答案，但輸入最多有 20000 個元素，不能作為正式解法。

function bruteForce(nums: number[]): number {
    let best = nums[0];

    for (let start = 0; start < nums.length; start++) {
        let product = 1;
        for (let end = start; end < nums.length; end++) {
            product *= nums[end];
            best = Math.max(best, product);
        }
    }

    return best;
}

第二版把「枚舉所有起點」壓縮成兩個極端狀態。每個元素只處理一次，時間為 O(n)，額外空間為 O(1)。輸出是一個數值，輸入陣列也不會被修改。這已經是漸進意義上的最佳時間，因為任一元素都可能改變答案，至少要讀取一次。

可執行測試

import assert from "node:assert/strict";

assert.equal(maxProduct([-2, 0, -1]), 0);
assert.equal(maxProduct([-3, 0, 1, -2]), 1);
assert.equal(maxProduct([-1, -2, -9, -6]), 108);
assert.equal(maxProduct([2, -5, -2, -4, 3]), 24);
assert.equal(maxProduct([-1, -1, -2]), 2);
assert.equal(maxProduct([-3]), -3);
assert.equal(maxProduct([0]), 0);

let cases = 0;
for (let length = 1; length <= 7; length++) {
    for (let encoded = 0; encoded < 5 ** length; encoded++) {
        let value = encoded;
        const nums = Array.from({ length }, () => {
            const element = value % 5 - 2;
            value = Math.floor(value / 5);
            return element;
        });
        const before = [...nums];

        assert.equal(maxProduct(nums), bruteForce(nums));
        assert.deepStrictEqual(nums, before);
        cases++;
    }
}

assert.equal(cases, 97655);

除了我原本列出的四組案例，這裡補上初版反例、單一負數與單一零。再用長度 1 到 7、元素為 -2 到 2 的 97655 組陣列與暴力解比對，並檢查輸入沒有被修改。這些測試已執行通過；有限範圍的測試是實作證據，不取代前面的不變量說明。

常見錯誤

• 只保留最大乘積，會漏掉負數乘負數翻成正數的可能。
• 把 best 初始化為 0，會讓 [-3] 錯誤回傳空陣列才有的 0。
• 使用更新後的 maxEndingHere 計算最小值，會把目前元素乘兩次。
• 遇到零時寫很多特殊分支。候選包含 num，零與重新開始都能由同一個轉移式處理。

這次學到的事

Maximum Subarray 只需要保存一個以目前位置結尾的最大和，因為加上同一個數字不會改變大小順序。這題使用乘法，負數會反轉順序，所以最大與最小都不能丟。

我需要記住的不是一段固定公式，而是先定義狀態：它代表哪些候選、一定在哪裡結束，以及下一輪為什麼只需要這些資訊。有了明確不變量，原本一大串正負號分支就能縮成兩行轉移。

參考資料

• LeetCode 152：Maximum Product Subarray：正式題意、範例與輸入限制。
• Node.js assert：可執行斷言。