[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）注意這里的數(shù)組是整型的，如果含有浮點(diǎn)數(shù)，就有可能出現(xiàn)0-1之間類似0.25這樣的小數(shù)，所以即使是全都是正數(shù)，也可以越乘越小。如果數(shù)組里的數(shù)字全為正數(shù)還好說(shuō)，因?yàn)榭梢杂们髮?duì)數(shù)的方式把求乘積轉(zhuǎn)化為求和，從而轉(zhuǎn)換為之前的Maximum Subarray。但是因?yàn)檫@題有負(fù)數(shù)和0的存在，所以求對(duì)數(shù)的方法行不通。

2）這題的測(cè)試用例里數(shù)組元素的絕對(duì)值都非常的小，而實(shí)際中如果真的連乘起來(lái)，最后數(shù)值越界很容易發(fā)生的。如果考慮這一點(diǎn)，要么估計(jì)得用類似Java里BigInteger類這樣的東西去避免越界。

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

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

綜合考慮如下：

1）如果當(dāng)前元素為正數(shù)，那么極大值只可能擴(kuò)大，所以應(yīng)該繼續(xù)擴(kuò)展當(dāng)前subarray：

此種情況簡(jiǎn)單，極大值應(yīng)該更新為原極大值乘以當(dāng)前元素，極小值更新為原極小值乘以當(dāng)前元素。全局最大值跟極大值比較。

2）如果當(dāng)前元素為負(fù)數(shù)，那么極大值可能會(huì)變小，所以不清楚應(yīng)該繼續(xù)擴(kuò)展當(dāng)前subarray還是新起一個(gè)subarray：

對(duì)于極大值的更新：如果擴(kuò)展當(dāng)前subarray，極大值為原極小值乘以當(dāng)前元素；如果另外新起一個(gè)subarray，由于當(dāng)前元素為負(fù)數(shù)，所以直接舍棄，根據(jù)規(guī)定，設(shè)為初始值1。由于這里原極小值不一定為負(fù)數(shù)，所以前者和后者之間比較沒(méi)有絕對(duì)的誰(shuí)大。

對(duì)于極小值的更新：如果擴(kuò)展當(dāng)前subarray，極小值為原極大值乘以當(dāng)前元素；如果另外新起一個(gè)subarray，極小值為當(dāng)前元素。不過(guò)由于之前極大值肯定大于1，所以前者肯定比后者大，所以極小值更新為原極大值乘以當(dāng)前元素。

最應(yīng)該小心的地方是更新全局最大值：這里的全局最大值不能和極大值比較，而應(yīng)該和極小值乘以當(dāng)前元素值比較，即擴(kuò)展當(dāng)前subarray的選擇比較。因?yàn)槿绻麡O大值此時(shí)為1，則并不是靠實(shí)實(shí)在在存在的，以當(dāng)前元素結(jié)尾的subarray獲得，而是靠舍棄當(dāng)前元素，寄希望于之后“可能”出現(xiàn)的新subarray。舉個(gè)例子，如果數(shù)組為{-2}，或者{-1, 0, -2}，那么無(wú)論如何是不會(huì)出現(xiàn)最大值為1這種情況的，因?yàn)樨?fù)數(shù)的后面沒(méi)有出現(xiàn)過(guò)正數(shù)。

3）如果當(dāng)前元素為0，那么包括一個(gè)0會(huì)使得極大值成為0，而按照操作規(guī)定，這里的極大值應(yīng)該大于等于1，所以應(yīng)該舍棄當(dāng)前元素，新起一個(gè)subarray。

對(duì)于極大值和極小值，由于新起一個(gè)subarray，全部還原為1。

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

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

思路二：如果數(shù)組里面沒(méi)有0，這題可以得到大大簡(jiǎn)化，所以我們可以先考慮如何處理一個(gè)不含0的數(shù)組。如此一來(lái)，不管怎么乘，絕對(duì)值都會(huì)增長(zhǎng)，所以最重要的就是要保證最后的乘積為正數(shù)。因此，可以分為兩種情況討論：

1）如果數(shù)組內(nèi)負(fù)數(shù)的個(gè)數(shù)為偶數(shù)，直接包括整個(gè)數(shù)組即可，最大乘積就是整個(gè)數(shù)組元素的乘積。

2）如果數(shù)組內(nèi)負(fù)數(shù)的個(gè)數(shù)為奇數(shù)，則應(yīng)該丟棄一個(gè)含有一個(gè)奇數(shù)的部分。為了使得所剩的數(shù)組最大限度的連續(xù)，無(wú)非就是兩種情況：

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

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

現(xiàn)在有了對(duì)這個(gè)題目簡(jiǎn)化版的解法，如果擴(kuò)展到這題的解法呢？很簡(jiǎn)單，首先掃一遍數(shù)組，以0為邊界，將整個(gè)數(shù)組分為若干個(gè)不含0的subarray，對(duì)于每個(gè)subarray逐一求解，并求得它們的最大值。另外，由于每個(gè)subarray的最大值可能都是負(fù)數(shù)，所以一旦有0出現(xiàn)，還應(yīng)該和0比較。代碼如下，start表示subarray的起始下標(biāo)，為-1的時(shí)候表示正在尋找下一個(gè)subarray。

這種解法比較繁瑣，而且由于為了思路清晰，這里我對(duì)數(shù)組進(jìn)行了多次掃描，其實(shí)可以將循環(huán)合并。不過(guò)無(wú)所謂了，O(n)的時(shí)間復(fù)雜度不會(huì)因?yàn)槎鄴吡艘粌杀槎兓?/p>

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

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)