# Solution: Maximum Product Subarray

Let's solve the Maximum Product Subarray problem using the Dynamic Programming pattern.

## Statement

Given an integer array, `nums`

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

**Constraints:**

$1\leq$ `nums.length`

$\leq10^3$ $-10\leq$ `nums[i]`

$10$ The product of any prefix or suffix ofÂ

`nums`

Â isÂ guaranteedÂ to fit in aÂ$32-bit$ Â integer.

## Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Letâ€™s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

### Naive approach

A naive approach is to calculate the product of every combination of contiguous subarrays and return the maximum of all the products.

Since we have to iterate over the array using a nested loop to find every combination, the time complexity of this approach will be `nums`

.

### Optimized approach using dynamic programming

The maximum product subarray problem can be solved more efficiently using dynamic programming by dividing the array and solving the subproblems. In this case, we can find the maximum product of a subarray from the start to any element by using the maximum product of the subarray from the start to its previous element. Using this approach, we donâ€™t need to calculate the previous products again; instead, we can use them from the stored products.

The simplest case is when the numbers in the array `nums`

are all positive numbers. In that case, we calculate the maximum product by multiplying all the numbers to get the `result`

. When we encounter zeros or negative numbers in the array, we have to use a slightly different approach, as explained below:

**Zeros**will reset the product to$0$ . If the`result`

is less than the product, update it with the product. Otherwise, the`result`

remains the same.**Negative numbers**can be a little challenging. When multiplied, a single negative number can flip the larger product into a smaller number. However, if we get another negative number, we can get the larger product again. Unlike zero, here we have a chance that our larger product can be restored if negative numbers are encountered twice.

To solve the problem above, follow the steps below:

Initialize

`maxSoFar`

with the first element of`nums`

. It will be used to track the maximum product up to an element. Initialize`minSoFar`

with the first element of`nums`

. It will be used to track the minimum product up to an element. Initialize`result`

with`maxSoFar`

.Now, iterate through the rest of the elements of the array as follows:

Update

`maxSoFar`

and`minSoFar`

by taking the maximum and minimum of the current value, the product of`maxSoFar`

and the current value, and the product of`minSoFar`

and the current value, respectively.Update

`result`

by taking the maximum of`maxSoFar`

and`result`

.

When all elements have been traversed, return

`result`

.

Letâ€™s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.