Bernice Waweru

Posted on

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.