Maximum Product Subarray

Problem:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed 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.

Approach 1 :

Brute force

Generate all subarray and return max product among them

    def maxProduct(self, nums: List[int]) -> int:
        max_=-1*float('inf')
        for i in range(len(nums)):
            prod=1
            for j in range(i,len(nums)):
                prod*=nums[j]
                if(max_<prod):
                    max_=prod
        return(max_)

Time :O(n²)

Space: O(1)

Approach 2:

Optimized solution.

In this we find the maximum and minimum ending at the current index. This is because the element at a position can be negative , positive and also a zero. We know that if a value at an index is negative, then to get maximum we need the minimum till previous index position, and to get minimum , we need maximum till the previous index and vice versa for a positive value at an index, said that , in each iteration we store the global maximum into a variable ‘global_’

def maxProduct(self, nums):
        global_,max_,min_=nums[0],nums[0],nums[0]
        i=1
        while(i<len(nums)):
            prev_max=max_
            max_=max(nums[i],max_*nums[i],min_*nums[i])
            min_=min(nums[i],prev_max*nums[i],min_*nums[i])
            global_=max(global_,max_)
            i+=1
        return global_

Time :O(n)

Space: O(1)

Approach 3:

Two pointer solution

The reason for using two pointer in over here is for the reason that, the final answer is subarray that either start from left of the array or from right. So we iterate through the array and constantly calculate the product of contiguous terms from left and right and also store the maximum among them to a variable and return the same . But the edge case here is the value zero . If zero is encountered while in any direction, then if this method is followed as such then all the future product will be zero in that direction .Therefore we reset the the product in that direction to 1 ,so that doesn’t alter the actual answer.

n=len(nums)
left,right=1,1
global_max=-1*float('inf')
for i in range(n):
  if(left==0):
    left=1
  if(right==0):
    right=1
  left*=nums[i]
  right=nums[n-1-i]
global_max=max(global_max,left,right)
return global_max