## Max Product Subarray Difficulty: Medium

#### 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 length `n` is a contiguous segment from `arr[i]` through `arr[j]` where `0<= i <= j <= n`.
• Array `arr[]` may contain both positive and negative integers. If the array contains all non-negative 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

1. Brute Force: Find all the subarray products and return the maximum.
2. 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 range `size(arr)`
• Calculate the product of `arr[i . . . j]` and update `maxProduct`.

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 `i-1`.

In short, One can have three options to make at any position in the array.

1. 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).
2. You can get the maximum product by multiplying the current element with minimum product calculated so far. (might work when current
element is negative).
3. The current element might be a starting position for maximum product subarray.

Solution Steps

• Initialize `maxProduct` with `arr` to store the maximum product so far.
• Initialize to variables `imax` and `imin` to store the maximum and minimum product till `i` .
• Iterate over the `arr` and for each negative element of arr, swap `imax` and `imin`. (Why?)
• Update `imax` and `imin` as discussed above and finally return `maxProduct`

Pseudo Code

``````int maxSubArrayProduct(int[] arr, int size) {
int maxProduct = arr
int imax = arr
int imin = arr
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` say `pref_arr` and the suffix product of `arr` say `suf_arr` and then return the maximum of pref_arr and `suf_arr` , will the solution work? If yes, then do you think that the above-discussed 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!