## 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 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

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

- 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`

with`arr[0]`

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[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`

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