Leetcode — 152. Maximum Product Subarray (中文)

問題連結: https://leetcode.com/problems/maximum-product-subarray/

題目給一整數陣列nums, 求陣列中連續位置數字(這些連續位置的數字們會組成子陣列)的最大乘積

範例
Input: [2,3,-2,4]
Output: 6
陣列中的 [2,3] 擁有整個陣列中可得的最大乘積6.

想法:

這問題其實跟Leetcode題53. Maximum Subarray很像, 我在這裡也有詳細解釋我們如何用O(n)時間內解第53題

簡單來說在第53題中, 我們被要求找陣列中連續位置數字的最大總和, 我們用一個temp變數來紀錄當我們當前子陣列結束在現在位置時, 可得到的最大總和, 在我們還沒做任何動作時, 只知道temp至少包含前一個位置的數字, 我們會檢查若我們可以擴展現有的子陣列時, 我們將會把現在位置數字加進去; 若現在子陣列總和為負數, 我們則會果斷放棄前面的總和們, 直接另闢新戰局(也就是讓現在位置數字成為新的子陣列的第一個數字)

然而我們在這題卻不能這樣做, 因為乘積造成負負得正的關係, 如果按照相同邏輯, 當我們發現當前子陣列總乘積為負數而放棄前面而另闢戰局的時候, 我們可能因此錯過了我們之後遇到另一個負數讓總乘積翻轉情勢的機會
而又因為這題是要求乘積, 若我們陣列中沒有碰到0的情況下, 其實整個乘積的絕對值絕對是子陣列越擴展, 數值越大

程式邏輯:

雖然我們無法完全按照我們在第52題的邏輯解這題, 但其實我們還是可以把原本解題邏輯做點改變, 讓我們仍然能夠在O(n)的時間複雜度內完成這題

與其用一個temp變數來控制目前我們到現在位置時可得到的子陣列的最大總乘積, 我們用兩個變數min 和 max 分別記錄 當子陣列結束在現在位置時, 我們可以得到的最大及最小總乘積

我們在現在位置的數字是負數的時候, 會把min和max變數的值互換, 因為我們知道當負數乘上越小的數字時, 才能得到更大的總乘積, 反之亦然

👷來看一個例子 假設nums= [3,4,-5,10,2,-3]:
(我們將會用rst變數來儲存目前遇過的最大總乘積)

有一點要注意的是 — 我們實際上在程式碼中並不會真的知道目前組成當前子陣列數字有誰, 畢竟我們只有min和max變數來紀錄兩個子陣列的最大或最小乘積, 但下列例子裡, 為了講解方便, 我還是會列出這些變數是由哪部分的子陣列組成

🔧Step 0. min和max變數的初始狀態, 在還沒有開始的情況, 我們直接假設由陣列中第一位數字所組成的”乘積”, 為最大和最小乘積
而因此 rst 變數初始值也為同樣數值.

Initial State

🔧Step 1. 當現在位置是1時, 數字為4
因為延展現有子陣列們的話, 總乘積會變大, 因此max部分的子陣列延展, 而min為了保持數字小, 就切開他跟前一位置的聯繫

step 1 result

💭因為找到目前最大乘積, rst 更新為12

🔧Step 2. 當現在位置是2時, 數字為-5
我們先要做的事情是對調min和max的值, 所以min=12, max=4
因為延展現有子陣列們的話, 總乘積會變小, 因此min部分的子陣列延展, 而max為了保持數字小, 就切開他跟前一位置的聯繫

step 2 result

🔧Step 3. 當現在位置是3時, 數字為10
因為原本min和max都是負數, 延展現有子陣列們的話, 都會因此變小, 因此只有min延展子陣列, max果斷切開與前一個位置的聯繫

step 3 result

🔧Step 4. 當現在位置是4時, 數字為2
因為min是負數, max是正數, 若我們延展現有子陣列們的話, 總乘積一個會變更小、一個會變更大, 因此max和min都決定延展前一個子陣列

step 4 result

💭碰到更大的總乘積了, 現在rst更新到20

🔧Step 5. 當現在位置是5時, 數字為-3
我們先要做的事情是對調min和max的值, 所以min=-1200, max=20
因為min是負數, max是正數, 若我們延展現有子陣列們的話, 總乘積一個會變小、一個會變大, 因此max和min都決定延展前一個子陣列

step 5 result

💭碰到更大的總乘積了, 現在rst更新到3600

🚧已完成走訪整個陣列了, 我們將回傳rst變數的值

以下為1ms 的程式碼, 贏過 94% —

public int maxProduct(int[] nums) {
        int n = nums.length;
        int rst = nums[0];
        int max = rst, min = rst;
        for(int i=1;i<n;i++)
        {
            int cur = nums[i];
            if(cur<0)//swap max and min
            {
                int temp = max;
                max = min;
                min = temp;
            }
            min = Math.min(cur*min, cur);
            max = Math.max(cur*max, cur);
            rst = Math.max(max, rst);
        }
        return rst;
    }