[LeetCode] 152. Maximum Product Subarray 求最大子數(shù)組乘積

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

這個(gè)求最大子數(shù)組乘積問題是由最大子數(shù)組之和 Maximum Subarray 演變而來，但是卻比求最大子數(shù)組之和要復(fù)雜，因?yàn)樵谇蠛偷臅r(shí)候，遇到0，不會(huì)改變最大值，遇到負(fù)數(shù)，也只是會(huì)減小最大值而已。而在求最大子數(shù)組乘積的問題中，遇到0會(huì)使整個(gè)乘積為0，而遇到負(fù)數(shù)，則會(huì)使最大乘積變成最小乘積，正因?yàn)橛胸?fù)數(shù)和0的存在，使問題變得復(fù)雜了不少。比如，現(xiàn)在有一個(gè)數(shù)組 [2, 3, -2, 4]，可以很容易的找出所有的連續(xù)子數(shù)組，[2]，[3]，[-2]，[4]，[2, 3]，[3, -2]，[-2, 4]，[2, 3, -2]，[3, -2, 4]，[2, 3, -2, 4]，然后可以很輕松的算出最大的子數(shù)組乘積為6，來自子數(shù)組 [2, 3]。但如何寫代碼來實(shí)現(xiàn)自動(dòng)找出最大子數(shù)組乘積呢，博主最先想到的方比較簡單粗暴，就是找出所有的子數(shù)組，然后算出每一個(gè)子數(shù)組的乘積，然后比較找出最大的一個(gè)，需要兩個(gè) for 循環(huán)，第一個(gè) for 遍歷整個(gè)數(shù)組，第二個(gè) for 遍歷含有當(dāng)前數(shù)字的子數(shù)組，就是按以下順序找出子數(shù)組: [2]，[2, 3]，[2, 3, -2]，[2, 3, -2, 4]，[3]，[3, -2]，[3, -2, 4]，[-2]，[-2, 4]，[4]，在本地測(cè)試的一些數(shù)組全部通過，于是興高采烈的拿到 OJ 上測(cè)試，結(jié)果喪心病狂的 OJ 用一個(gè)有 15000 個(gè)數(shù)字的數(shù)組來測(cè)試，然后說程序的運(yùn)行時(shí)間超過了要求值，一看代碼，果然如此，時(shí)間復(fù)雜度 O(n2), 得想辦法只用一次循環(huán)搞定。想來想去想不出好方法，于是到網(wǎng)上搜各位大神的解決方法。其實(shí)這道題最直接的方法就是用 DP 來做，而且要用兩個(gè) dp 數(shù)組，其中 f[i] 表示子數(shù)組 [0, i] 范圍內(nèi)并且一定包含 nums[i] 數(shù)字的最大子數(shù)組乘積，g[i] 表示子數(shù)組 [0, i] 范圍內(nèi)并且一定包含 nums[i] 數(shù)字的最小子數(shù)組乘積，初始化時(shí) f[0] 和 g[0] 都初始化為 nums[0]，其余都初始化為0。那么從數(shù)組的第二個(gè)數(shù)字開始遍歷，那么此時(shí)的最大值和最小值只會(huì)在這三個(gè)數(shù)字之間產(chǎn)生，即 f[i-1]*nums[i]，g[i-1]*nums[i]，和 nums[i]。所以用三者中的最大值來更新 f[i]，用最小值來更新 g[i]，然后用 f[i] 來更新結(jié)果 res 即可，由于最終的結(jié)果不一定會(huì)包括 nums[n-1] 這個(gè)數(shù)字，所以 f[n-1] 不一定是最終解，不斷更新的結(jié)果 res 才是，參見代碼如下：

解法一：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], n = nums.size();
        vector<int> f(n, 0), g(n, 0);
        f[0] = nums[0];
        g[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            f[i] = max(max(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
            g[i] = min(min(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]);
            res = max(res, f[i]);
        }
        return res;
    }
};

我們可以對(duì)上面的解法進(jìn)行空間上的優(yōu)化，以下摘自 OJ 官方解答，大體思路相同，寫法更加簡潔：

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

Let us denote that:

f(k) = Largest product subarray, from index 0 up to k.

Similarly,

g(k) = Smallest product subarray, from index 0 up to k.

Then,

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )

There we have a dynamic programming formula. Using two arrays of size n, we could deduce the final answer as f(n-1). Since we only need to access its previous elements at each step, two variables are sufficient.

public int maxProduct(int[] A) {
   assert A.length > 0;
   int max = A[0], min = A[0], maxAns = A[0];
   for (int i = 1; i < A.length; i++) {
      int mx = max, mn = min;
      max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
      min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
      maxAns = Math.max(max, maxAns);
   }
   return maxAns;
}

根據(jù)上述描述可以寫出代碼如下：

解法二：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int res = nums[0], mn = nums[0], mx = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int tmax = mx, tmin = mn;
            mx = max(max(nums[i], tmax * nums[i]), tmin * nums[i]);
            mn = min(min(nums[i], tmax * nums[i]), tmin * nums[i]);
            res = max(res, mx);
        }
        return res;
    }
};

下面這種方法也是用兩個(gè)變量來表示當(dāng)前最大值和最小值的，但是沒有無腦比較三個(gè)數(shù)，而是對(duì)于當(dāng)前的 nums[i] 值進(jìn)行了正負(fù)情況的討論：

2. 當(dāng)遍歷到一個(gè)負(fù)數(shù)時(shí)，先用一個(gè)變量t保存之前的最大值 mx，然后此時(shí)的最大值等于之前最小值乘以這個(gè)負(fù)數(shù)和當(dāng)前負(fù)數(shù)中的較大值，此時(shí)的最小值等于之前保存的最大值t乘以這個(gè)負(fù)數(shù)和當(dāng)前負(fù)數(shù)中的較小值。

3. 在每遍歷完一個(gè)數(shù)時(shí)，都要更新最終的最大值。

解法三：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], mx = res, mn = res;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                mx = max(mx * nums[i], nums[i]);
                mn = min(mn * nums[i], nums[i]);
            } else {
                int t = mx;
                mx = max(mn * nums[i], nums[i]);
                mn = min(t * nums[i], nums[i]);
            }
            res = max(res, mx);
        }
        return res;
    }
};

下面這道題使用了一個(gè) trick 來將上面解法的分情況討論合成了一種，在上面的解法中分析了當(dāng) nums[i] 為正數(shù)時(shí)，最大值和最小值的更新情況，為負(fù)數(shù)時(shí)，稍有不同的就是最小值更新時(shí)要用到之前的最大值，而不是更新后的最大值，所以才要用變量t來保存之前的結(jié)果。而下面這種方法的巧妙處在于先判斷一個(gè)當(dāng)前數(shù)字是否是負(fù)數(shù)，是的話就交換最大值和最小值。那么此時(shí)的 mx 就是之前的 mn，所以 mx 的更新還是跟上面的方法是統(tǒng)一的，而在在更新 mn 的時(shí)候，之前的 mx 已經(jīng)保存到 mn 中了，而且并沒有改變，所以可以直接拿來用，不得不說，確實(shí)叼啊，參見代碼如下：

解法四：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], mx = res, mn = res;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < 0) swap(mx, mn);
            mx = max(nums[i], mx * nums[i]);
            mn = min(nums[i], mn * nums[i]);
            res = max(res, mx);
        }
        return res;
    }
};

再來看一種畫風(fēng)不太一樣的解法，這種解法遍歷了兩次，一次是正向遍歷，一次是反向遍歷，相當(dāng)于正向建立一個(gè)累加積數(shù)組，每次用出現(xiàn)的最大值更新結(jié)果 res，然后再反響建立一個(gè)累加積數(shù)組，再用出現(xiàn)的最大值更新結(jié)果 res，注意當(dāng)遇到0的時(shí)候，prod 要重置為1。至于為啥正反兩次遍歷就可以得到正確的結(jié)果了呢？主要還是由于負(fù)數(shù)個(gè)數(shù)的關(guān)系，因?yàn)樨?fù)數(shù)可能會(huì)把最大值和最小值翻轉(zhuǎn)，那么當(dāng)有奇數(shù)個(gè)負(fù)數(shù)時(shí)，如果只是正向遍歷的話，可能會(huì)出錯(cuò)，比如 [-1, -2, -3]，累加積會(huì)得到 -1，2，-6，看起來最大值只能為2，其實(shí)不對(duì)，而如果我們?cè)俜聪騺硪槐?，累加積為 -3，6，-6，就可以得到6了。所以當(dāng)負(fù)數(shù)個(gè)數(shù)為奇數(shù)時(shí)，首次出現(xiàn)和末尾出現(xiàn)的負(fù)數(shù)就很重要，有可能會(huì)是最大積的組成數(shù)字，所以遍歷兩次就不會(huì)漏掉組成最大值的機(jī)會(huì)，參見代碼如下：

解法五：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0], prod = 1, n = nums.size();
        for (int i = 0; i < n; ++i) {
            res = max(res, prod *= nums[i]);
            if (nums[i] == 0) prod = 1;
        }
        prod = 1;
        for (int i = n - 1; i >= 0; --i) {
            res = max(res, prod *= nums[i]);
            if (nums[i] == 0) prod = 1;
        }
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/152

類似題目：

Maximum Subarray

House Robber

Product of Array Except Self

Maximum Product of Three Numbers

Subarray Product Less Than K

參考資料：

https://leetcode.com/problems/maximum-product-subarray/

https://leetcode.com/problems/maximum-product-subarray/discuss/48302/2-passes-scan-beats-99

https://leetcode.com/problems/maximum-product-subarray/discuss/48261/share-my-dp-code-that-got-ac

https://leetcode.com/problems/maximum-product-subarray/discuss/48252/sharing-my-solution-o1-space-on-running-time

https://leetcode.com/problems/maximum-product-subarray/discuss/48230/possibly-simplest-solution-with-on-time-complexity

https://leetcode.com/problems/maximum-product-subarray/discuss/48389/my-concise-dp-on-java-solution-with-o1-extra-space

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(152.求最大子數(shù)組乘積)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求最大子數(shù)組乘積內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論