[toc]

**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 <= nums.length <= 2 * 10`

^{4}`-10 <= nums[i] <= 10`

- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

NOTE: What is a contiguous subarray?Subarrays are simply subsets of a given array. If the indices of the elements in the subarray are adjacent, i.e. they lie within a continuous range then the subarray is called a contiguous subarray. Example: array = [10, 20, 30, 40, 50]β¦Ώ subarray = [20,30,40] β¦Ώ subsequence = [10, 30, 50] —-> this is a subsequence but not a contiguous subarray. |

**Examples**

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

Example 1:Input: nums = [2, 3, -2, 4] Output: 6 Explanation: The sub-array [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 sub-array. Example 3:Input: nums = [6, -3, -10, 0, 2] Output: 180 Explanation: The sub-array [6, -3, -10] has the largest product, 180. Example 4:Input: nums = [-2, -3, 0, -2, -40] Output: 80 Explanation: The sub-array [-2, -40] has the largest product, 80. Example 5:Input: nums = [10, 20] Output: 200 Explanation: The sub-array [10, 20] has the largest product, 200. |

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

**Brute force Method: Linear Traversal**

**Approach:** The idea of this approach is to traverse all the contiguous sub-arrays in the given array and store the product of these arrays. Further, return the maximum product among all the calculated products.

**Algorithm:**

- Calculate the length of the array.
- Initialize a variable β
`res`

β and store the initial value as the initial result. - Keep traversing the array and updating the β
`res`

β variable every time in order to keep track of the maximum product. - Finally, update the variable for the
`(n-1)th`

index and return it.

**Solution:**

def max_product(nums): n = len(nums) res = nums[0] 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.

# Example 1nums = [2, 3, -2, 4] print(max_product(nums)) # 6# Example 2nums = [-2, 0, -1] print(max_product(nums)) # 0# Example 3nums = [6, -3, -10, 0, 2] print(max_product(nums)) # 180# Example 4nums = [-2, -3, 0, -2, -40] print(max_product(nums)) # 80# Example 5nums = [10, 20] print(max_product(nums)) # 200 |

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).**

**Kadaneβs Algorithm**

**Kadaneβs Algorithm**

**Approach:** In this approach, you have to keep track of the `maximum`

and `minimum`

product in the array. You have to keep checking whether the element of the array is negative. If yes, then you have to swap the values of the values of `minimum`

and `maximum`

products. Finally, compare these variables to get the maximum product.

**Algorithm:**

- Initialize two variables- β
`max_v`

β and β`min_v`

β that will store the maximum and minimum product of the array, respectively. - Check if the next number in the array is negative. If yes, swap the values of β
`max_v`

β and β`min_v`

β - After you have completed the traversal, the variables will store the maximum and minimum products.
- Calculate the maximum product of the array and return it.

**Solution:**

def max_product(nums): n = len(nums) min_v = nums[0] max_v = nums[0] prod = nums[0] 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.

# Example 1nums = [2, 3, -2, 4] print(max_product(nums)) # 6# Example 2nums = [-2, 0, -1] print(max_product(nums)) # 0# Example 3nums = [6, -3, -10, 0, 2] print(max_product(nums)) # 180# Example 4nums = [-2, -3, 0, -2, -40] print(max_product(nums)) # 80# Example 5nums = [10, 20] print(max_product(nums)) # 200 |

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)**.

**Scanning The Array From Both Ends**

**Scanning The Array From Both Ends****Approach:** The idea of this approach is to keep track of the maximum product in the given array by traversing it twice, i.e. once from left to right and then from right to left. To traverse the array from the right end to the left end, you can simply reverse the array. You have to traverse each array and keep multiplying every new number derived in each iteration with the value at its previous index. You need to do this for both arrays until you have traversed all the elements. Finally compare all the elements to find the maximum product among them.

**Algorithm:**

- Initialize two arrays – “
`ltor`

” (stores elements of given array from left to right) and “`rtol`

” (stores elements of given array from right to left). - Traverse the array and keep calculating the product of each number with the previous number. Store it in the variables.
- Calculate the maximum value (product) among both these arrays and return it.

The following diagram illustrates the above mentioned algorithm with the help of an example.

**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.

# Example 1nums = [2, 3, -2, 4] print(max_product(nums)) # 6# Example 2nums = [-2, 0, -1] print(max_product(nums)) # 0# Example 3nums = [6, -3, -10, 0, 2] print(max_product(nums)) # 180# Example 4nums = [-2, -3, 0, -2, -40] print(max_product(nums)) # 80# Example 5nums = [10, 20] print(max_product(nums)) # 200 |

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

**Recommended: ** **Finxter Computer Science Academy**

- Do you want to master the most popular Python IDE fast?
- This course will take you from beginner to expert in PyCharm in ~90 minutes.
- For any software developer, it is crucial to master the IDE well, to write, test and debug high-quality code with little effort.