# [Interview Question] How to Solve The Maximum Product Subarray Problem in Python?

Company Tags: Amazon, Microsoft

## Problem Statement:

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.

⚠️Constraints:

1. `1 <= nums.length <= 2 * 104`
2. `-10 <= nums[i] <= 10`
3. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

## Examples

Let us look at some examples to improve our understanding of the problem.

Now that you have a clear understanding of the problem, let’s dive into the methods:

## Brute force Method: Linear Traversal

Approach: The basic idea of this approach is to traverse all the contiguous sub-arrays in the array list and store the product of these arrays. Further, return the max product among these.

Algorithm:

1. Calculate the length of the array.
2. Initialize a variable “`res`” and store the initial value as the initial result.
3. Keep traversing the array and updating the “`res`” variable every time in order to keep track of the maximum product.
4. Finally, update the variable for the `(n-1)th` index and return it.

Solution:

```def max_product(nums):
n = len(nums)
res = nums
for i in range(n):
prod = nums[i]

for j in range(i + 1, n):
res = max(res, prod)
prod = prod * nums[j]

res = max(res, prod)

return res```

Test Case Analysis: Let’s run this code on our example.

Hurrah! It passed all the test cases.

Complexity Analysis: As we traversed the array for each sub-array, the time complexity of this method is O(n^2).

Approach: In this approach, you have to keep track of the maximum and minimum product in the array. Keep checking whether the element of the array is negative. If yes, then the values of minimum and maximum products get swapped. Then finally, compare these variables to get the maximum product.

Algorithm:

1. Initialize two variables- “max_v” and “min_v” that will store the maximum and minimum product of the array, respectively.
2. Check if the next number in the array is negative. If yes, swap the values of “max_v” and “min_v”
3. After you have completed the traversal, the variables will store the maximum and minimum products.
4. Calculate the maximum product of the array and return it.

Solution:

```def max_product(nums):
n = len(nums)
min_v = nums
max_v = nums
prod = nums

for i in range(1, n, 1):
if (nums[i] < 0):
temp = max_v
max_v = min_v
min_v = temp

max_v = max(nums[i], max_v * nums[i])
min_v = min(nums[i], min_v * nums[i])

prod = max(prod, max_v)

return prod```

Test Case Analysis: Let’s run this code on our example.

Yeah! It passed all the test cases.

Complexity Analysis: As we traverse the array only once, the time complexity of this method is O(n).

## [Alternate Approach]: Scanning Twice

Approach: The idea of this approach is to keep track of the maximum product in the array two times- from left to right and from right to left. You have to multiply each new number on both sides and compare to find the maximum product.

Algorithm:

1. Initialize two variables- “ltor” (left to right) and “rtol” (right to left) at the start and end of the array.
2. Traverse the array and keep calculating the product of each number with the previous number. Store it in the variables.
3. Calculate the max product in both these arrays and return the max product among those two.

Solution:

```def max_product(nums):
n = len (nums)
ltor = nums
rtol = nums[::-1]

for i in range(1, n):

ltor[i] = ltor[i] * (ltor[i-1] or 1)
rtol[i] = rtol[i] * (rtol[i-1] or 1)
return max (max (ltor), max (rtol))
```

Test Case Analysis: Let’s run this code on our example.

Yeah! It passed all the test cases.

Complexity Analysis: As we traverse the array only once, the time complexity of this method is O(n).

## Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Post Credits: Shubham Sayon and Rashi Agarwal 