152. Maximum Product Subarray

152. Maximum Product Subarray (Medium)

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.

Companies:
LinkedIn, Google, Amazon, Microsoft, Adobe

Related Topics:
Array, Dynamic Programming

Similar Questions:

• Maximum Subarray (Easy)
• House Robber (Easy)
• Product of Array Except Self (Medium)
• Maximum Product of Three Numbers (Easy)
• Subarray Product Less Than K (Medium)

Solution 1. Two Pointers

The problem is the same as finding the longest subarray with even number negative numbers without 0.

We can use two pointers.

• the fast pointer keeps reading number until it reaches 0 or end of array; meanwhile, we keep updating answer with the greatest product we've seen.
• if the product is negative, we move the slow pointer until the product becomes positive, and update the answer if it's greater.
• we move both pointers to the next non-zero number and loop until the fast pointer reaches the end.

// OJ: https://leetcode.com/problems/maximum-product-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxProduct(vector<int>& A) {
        int ans = A[0], N = A.size(), j = 0;
        while (j < N) {
            int i = j, prod = 1;
            while (j < N && A[j] != 0) {
                prod *= A[j++];
                ans = max(ans, prod);
            }
            if (j < N) ans = max(ans, 0);
            while (i < N && prod < 0) {
                prod /= A[i++];
                if (i != j) ans = max(ans, prod);
            }
            while (j < N && A[j] == 0) ++j;
        }
        return ans;
    }
};

Solution 2. DP

Let max[i] be the maximum product of subarrays ending at A[i], min[i] be the minimum product of subarrays ending at A[i].

max[i] = max(A[i], A[i] * max[i - 1], A[i] * min[i - 1])
min[i] = min(A[i], A[i] * max[i - 1], A[i] * min[i - 1])

// OJ: https://leetcode.com/problems/maximum-product-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxProduct(vector<int>& A) {
        int maxProd = 1, minProd = 1, ans = INT_MIN;
        for (int n : A) {
            int a = n * maxProd, b = n * minProd;
            maxProd = max({n, a, b});
            minProd = min({n, a, b});
            ans = max(ans, maxProd);
        }
        return ans;
    }
};

Note

Similar problem: 1567. Maximum Length of Subarray With Positive Product (Medium)