Maximum Product Subarray

Instructions

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

Example

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

Approach

If you have solved the Maximum SubArray Sum, then you have some idea of how we can solve this problem.

We keep track of the minimum and maximum product of the numbers visited so far. Then we can make comparisons and update the variables appropriately.

Python Implementation

def maxProduct(self, nums: List[int]) -> int:
    if len(nums) == 0:
       return 0
    max_so_far = nums[0]
    min_so_far = nums[0]
    result = max_so_far
    for i in range(1, len(nums)):
        curr = nums[i]
        temp_max = max(curr, max_so_far * curr, min_so_far * curr)
        min_so_far=min(curr, max_so_far * curr, min_so_far * curr)
        max_so_far = temp_max

        result = max(max_so_far, result)
    return result

I hope you found this helpful.