Max Product Subarray
Difficulty: Medium
Asked in: Amazon, Microsoft
Understanding The Problem
Problem Description
You are given an array
arr[]
with
n
elements. Write a program to find the
contiguous subarray which has the largest product.
Problem Note

A contiguous subarray of an array
arr[]
of lengthn
is a contiguous segment fromarr[i]
througharr[j]
where0<= i <= j <= n
. 
Array
arr[]
may contain both positive and negative integers. If the array contains all nonnegative numbers, the maximum subarray is the product of the entire array.
Example 1
Input: arr[] = [9, 6, 10, 3]
Output: 30
Explanation: The subarray [10, 3] has the maximum product.
Example 2
Input: arr[] = [6, 3, 10, 0, 2]
Output: 180
Explanation: The subarray [6, 3, 10] has the maximum Product.
Example 3
Input: arr[] = [2, 3, 0, 2, 40]
Output: 80
Explanation: The subarray [2, 40] has the maximum product.
Solutions
 Brute Force: Find all the subarray products and return the maximum.

Dynamic Programming:
Keep track of the minimum and maximum products while scanning
arr
.
You may try the problem here.
1. Brute Force
To find the maximum product of a subarray in the given array we can calculate for all the possible products and return the maximum.
Solution Step

Create
maxProduct
to store the maximum subarray product. 
For every pair of integers
(i, j)
in the rangesize(arr)

Calculate the product of
arr[i . . . j]
and updatemaxProduct
.
Pseudo Code
int maxSubArrayProduct(int[] arr, int size) {
int maxProduct = INT_MIN
for(int i=0 to i < size){
localProduct = 1
for(int j=i to j < size){
localProduct = localProduct * arr[j]
}
maxProduct = max(maxProduct, localProduct)
}
return maxProduct
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(1)
Critical Ideas To Think

Why we initialized
localProduct
with 1? 
What if we initialized
maxProduct
with 1?  Dry run this on some sample test cases and try to optimize the solution.
2. Dynamic Programming
Imagine that we have both
max_prod[i]
and
min_prod[i]
i.e. max product ending at
i
and min product ending at
i
.
Now if we have a negative number at
arr[i+1]
and if
min_prod[i]
is negative, then the product of the two will be positive and can potentially be the largest product. So, the key point here is to maintain both the
max_prod
and
min_prod
such that at iteration
i
, they refer to the max and min product ending at index
i1
.
In short, One can have three options to make at any position in the array.

You can get the maximum product by multiplying the current element with the maximum product calculated so far. (might work when current
element is positive). 
You can get the maximum product by multiplying the current element with minimum product calculated so far. (might work when current
element is negative).  The current element might be a starting position for maximum product subarray.
Solution Steps

Initialize
maxProduct
witharr[0]
to store the maximum product so far. 
Initialize to variables
imax
andimin
to store the maximum and minimum product tilli
. 
Iterate over the
arr
and for each negative element of arr, swapimax
andimin
. (Why?) 
Update
imax
andimin
as discussed above and finally returnmaxProduct
Pseudo Code
int maxSubArrayProduct(int[] arr, int size) {
int maxProduct = arr[0]
int imax = arr[0]
int imin = arr[0]
for(int i=1 to i<size) {
if(arr[i]<0)
swap(imax,imin)
imax = max(arr[i], imax * arr[i])
imin = min(arr[i],imin * arr[i])
maxProduct = max(maxProduct, imax)
}
return maxProduct
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
 What if the array has just positive numbers including zero?

If we store the prefix product of
arr
saypref_arr
and the suffix product ofarr
saysuf_arr
and then return the maximum of pref_arr andsuf_arr
, will the solution work? If yes, then do you think that the abovediscussed approach is analogous to it?
Comparison of Solutions
Suggested Problems to Solve
 Product of Array Except Self
 Maximum Product of Three Numbers
 Subarray Product Less Than K
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding!
Enjoy Algorithms!