# Others - Maximum Product Subarray

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DP

## Problem

Given an integer array `nums`

, find a subarray that has the largest product, and return *the product*.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

1
2
3

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

**Example 2:**

1
2
3

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

## Solution

It’s evident that we can solve the problem just by traversing the array one time, but the only problem is the `-`

sign which will shift the result. The `-`

sign will reverse the result, that is, it will change the largest product to smallest one and the smallest one to largest one. Since we won’t have any control over it, why don’t we track both and finally find out the max one.

So let’s create two variables `smallest`

and `largest`

. We need to set them to `1`

and not `0`

since we are working with product here.

1

smallest, largest = 1, 1

We also need to keep track of the `largest`

at every iteration as in case there is only one negative number then at the end of the loop the `largest`

value may not be largest. Try to solve `[2,3,-2,4]`

and you will see at the end the `largest`

is `4`

, however the correct result is `2 x 3 = 6`

and not `4`

.

The other important trick to understand which value to initialize this with ? We know that the `nums`

array can have any number, positives or negatives.

Say there is just one number and that is negative `[-5]`

then the `max_product`

must be `-5`

. So we can initially say, the `max(nums)`

is the `max_product`

without knowing anything about the `nums`

array.

1

max_product = max(nums)

Now, please refer the diagram below. Here we are going to keep track of `min`

and `max`

product for every iteration of the loop. We need to compare 3 values.

`MAX = max ( largest*nums[i],smallest*nums[i], nums[i])`

`MIN = max ( largest*nums[i],smallest*nums[i], nums[i])`

We need to consider the current value (`nums[i]`

) as well for finding `MIN`

and `MAX`

. Notice above we have `-2`

as max and `-12`

as min. Now `4`

could be the next `MAX`

and not `-8`

.

1
2
3
4
5
6

for i in range(len(nums)):
MAX = max ( largest*nums[i],smallest*nums[i], nums[i])
MIN = min ( largest*nums[i],smallest*nums[i], nums[i])
largest = MAX
smallest = MIN
max_product= max(max_product,largest)

We have one more edge case to take care. Whenever `nums[i]==0`

we need to reset `largest`

and `smallest`

otherwise all the products going forward will be `0`

.

1
2
3
4
5
6

for i in range(len(nums)):
if nums[i] ==0:
largest=1
smallest=1
continue
MAX = max( .... )

Finally just return the `max_product`

.

1

return max_product

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def max_product(nums):
smallest, largest = 1, 1
max_product = max(nums)
for i in range(len(nums)):
if nums[i] ==0:
largest=1
smallest=1
continue
MAX = max ( largest*nums[i],smallest*nums[i], nums[i])
MIN = min ( largest*nums[i],smallest*nums[i], nums[i])
largest = MAX
smallest = MIN
max_product= max(max_product,largest)
return max_product