# 152. Maximum Product Subarray Leetcode Solution

## Maximum Product Subarray Leetcode 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.

## Maximum Product Subarray Leetcode Solution :

### Constraints :

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

### Example 1:

• Input: nums = [-2,0,-1]
• Output: 0

Intuition :

This problem is really similar to Maximum Subarray except instead of a sum it’s a product, so naturally, a DP solution also comes to mind.

Approach :

In this question, we need to keep track of two subarrays: the subarray with the maximum product so far and the subarray with the minimum product so far. Why do we need to keep track of the minimum product? To handle the negative case. Let’s revisit that negative subarray again:

nums = [2, -2, 2, -2]
When we are 3 indices in [2, -2, 2], the running product of all 3 elements is negative. The maximum product so far is 2 (just a singular element in the subarray), but the minimum subarray is [2 -2 2] with a product of -8. Now, when we calculate the solution for all 4 indices, we consider both the max product and the min product to get 16.

There are 3 DP cases to consider

1. Restart new subarray
• Set the running product to be just the current element
• This handles the case with 0s
2. Add current element to the current subarray with the minimum product
• Set running product to be minimum_product * value
3. Add current element to the current subarray with the maximum product
• Set running product to be maximum_product * value

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others