LeetCode 152 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.

Diffculty Medium

Similar Problems

[LeetCode 53] Maximum Subarray Medium [LeetCode 198] House Robber Easy [LeetCode 238] Product of Array Except Self Medium

Analysis

思路一 虽说类似于最大子数组和问题，但实际上有很多细节不同。因为当前最大子数组和只与前一个的最大和有关，但是乘积则不同。乘积会由于负负得正的原因，我们不仅会记录当前最大乘积还要记录当前最小乘积。

思路二 这一题目可以用动态规划求解。其实，上述思路本质上也是动态规划，只是解题所表现出来的具体形式跟动态规划不太一样。 假设数组为 num[]，考虑到可能存在负数的情况，我们用 Max 来表示以 num[i] 结尾的最大连续乘积值，用 Min 表示以 num[i] 结尾的最小连续乘积值。 状态转移方程为：

初始状态为 Max[0] = Min[0] = num[0] 。

Solutions

解法一 Maximum Product Subarray 其实只需要不断地记录两个值，max 和 min。 max 是到当前为止最大的正 product，min 是到当前为止最小的负 product，或者 1。

int maxProduct(vector<int>& A) {
    int x = 1;
    int max = 1;
    int min = 1;
    for (int i = 0; i < A.szie(); i++) {
        if (A[i] == 0) {
            max = 1;
            min = 1;
        } else if (A[i] > 0) {
            max = max * A[i];
            min = min(min * A[i], 1);
        } else {
            int temp = max;
            max = max(min * A[i], 1);
            min = temp * A[i];
        }
        if (max > x)
            x = max;
    }
    return x;
}

解法二

class Solution {
public:
    int maxProduct(vector<int>& A) {
        int n = A.size();
        int curMax = A[0], curMin = A[0];
        for(int i = 1; i < n; ++i){
            int tmpMax = curMax;
            curMax = max(max(curMax*A[i], curMin*A[i]), A[i]);
            curMin = min(min(curMax*A[i], curMin*A[i]), A[i]);
        }
        return max(curMax, curMin);
    }
};

Reference