152. Maximum Product Subarray

Description

Given an integer array nums, find a contiguous non-empty subarray within the array 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.

A subarray is a contiguous subsequence of the array.

 

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 prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

maximum-product-subarray.py

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = pos = neg = nums[0]

        for x in nums[1:]:
            if x < 0:
                pos, neg = neg, pos

            pos = max(x, pos * x)
            neg = min(x, neg * x)

            res = max(res, pos)

        return res

maximum-product-subarray.cpp

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; 
    }
};