[LeetCode] Maximum Product Subarray的兩種思路

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

1）注意這里的數組是整型的，如果含有浮點數，就有可能出現0-1之間類似0.25這樣的小數，所以即使是全都是正數，也可以越乘越小。如果數組里的數字全為正數還好說，因為可以用求對數的方式把求乘積轉化為求和，從而轉換為之前的Maximum Subarray。但是因為這題有負數和0的存在，所以求對數的方法行不通。

2）這題的測試用例里數組元素的絕對值都非常的小，而實際中如果真的連乘起來，最后數值越界很容易發生的。如果考慮這一點，要么估計得用類似Java里BigInteger類這樣的東西去避免越界。

言歸正傳，這題我覺得至少有兩種思路求解。

思路一：類似Maximum Subarray的解題思路，在遍歷過程中，不斷更新以當前元素為終點的subarray的乘積極大值（下面簡稱極大值）和最大值。本質上無非就是要做出一個二選一：要么繼續把當前遍歷的元素算上，擴展當前的subarray，要么就重新開始一個subarray。此外，如何更新最大值？由于有整數，負數和0的存在，需要分為三種情況，并且還需要維護一個極小值。為了方便連乘操作，這里規定維護的最大乘積必須大于等于1，即不能等于0。另外需要注意，在沒有遍歷到負數之前，極小值這里其實和極大值是一樣大的（不考慮為0的情況），也可以是正數。

綜合考慮如下：

1）如果當前元素為正數，那么極大值只可能擴大，所以應該繼續擴展當前subarray：

此種情況簡單，極大值應該更新為原極大值乘以當前元素，極小值更新為原極小值乘以當前元素。全局最大值跟極大值比較。

2）如果當前元素為負數，那么極大值可能會變小，所以不清楚應該繼續擴展當前subarray還是新起一個subarray：

對于極大值的更新：如果擴展當前subarray，極大值為原極小值乘以當前元素；如果另外新起一個subarray，由于當前元素為負數，所以直接舍棄，根據規定，設為初始值1。由于這里原極小值不一定為負數，所以前者和后者之間比較沒有絕對的誰大。

對于極小值的更新：如果擴展當前subarray，極小值為原極大值乘以當前元素；如果另外新起一個subarray，極小值為當前元素。不過由于之前極大值肯定大于1，所以前者肯定比后者大，所以極小值更新為原極大值乘以當前元素。

最應該小心的地方是更新全局最大值：這里的全局最大值不能和極大值比較，而應該和極小值乘以當前元素值比較，即擴展當前subarray的選擇比較。因為如果極大值此時為1，則并不是靠實實在在存在的，以當前元素結尾的subarray獲得，而是靠舍棄當前元素，寄希望于之后“可能”出現的新subarray。舉個例子，如果數組為{-2}，或者{-1, 0, -2}，那么無論如何是不會出現最大值為1這種情況的，因為負數的后面沒有出現過正數。

3）如果當前元素為0，那么包括一個0會使得極大值成為0，而按照操作規定，這里的極大值應該大于等于1，所以應該舍棄當前元素，新起一個subarray。

對于極大值和極小值，由于新起一個subarray，全部還原為1。

對于全局最大值的更新，這里和2）類似。由于極大值的獲取是寄希望于之后“可能”出現的新subarray，所以更新全局最大值的時候不能和此時的極大值1進行比較，而應該和實實在在的0比較。

以下代碼，loc_min和loc_max表示極小值和極大值，glb_max為所求。

思路二：如果數組里面沒有0，這題可以得到大大簡化，所以我們可以先考慮如何處理一個不含0的數組。如此一來，不管怎么乘，絕對值都會增長，所以最重要的就是要保證最后的乘積為正數。因此，可以分為兩種情況討論：

1）如果數組內負數的個數為偶數，直接包括整個數組即可，最大乘積就是整個數組元素的乘積。

2）如果數組內負數的個數為奇數，則應該丟棄一個含有一個奇數的部分。為了使得所剩的數組最大限度的連續，無非就是兩種情況：

2.1) 丟棄掉數組里出現的第一個負數和在它之前的元素。例如{1, 2, -3, 4, -5, 6, 7}，由于第一個負數為-3，丟棄最開始的1,2和-3。

2.2) 丟棄掉數組里出現的最后一個負數和在它之后的元素。用上個例子，由于最后一個負數為-5，丟棄最后的-5,6和7。

現在有了對這個題目簡化版的解法，如果擴展到這題的解法呢？很簡單，首先掃一遍數組，以0為邊界，將整個數組分為若干個不含0的subarray，對于每個subarray逐一求解，并求得它們的最大值。另外，由于每個subarray的最大值可能都是負數，所以一旦有0出現，還應該和0比較。代碼如下，start表示subarray的起始下標，為-1的時候表示正在尋找下一個subarray。

這種解法比較繁瑣，而且由于為了思路清晰，這里我對數組進行了多次掃描，其實可以將循環合并。不過無所謂了，O(n)的時間復雜度不會因為多掃了一兩遍而變化。

比較這兩種解法，第一種適用性更廣，其實對浮點數也同樣適用，而第二種則不能允許有0-1之間的小數。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈