152. Maximum Product Subarray

Problem Link

Description

---

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Solution

---

Python3

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        N = len(nums)
        pos = neg = res = nums[0]
 
        for i in range(1, N):
            if nums[i] < 0:
                pos, neg = neg, pos
            
            pos = max(nums[i], nums[i] * pos)
            neg = min(nums[i], nums[i] * neg)
 
            res = max(res, pos)
        
        return res

C++

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