Maximum Product Subarray

Medium · 1-D Dynamic Programming

You are given an array of integers. Find the contiguous subarray (containing at least one number) that has the largest product, and return that product. Negative numbers can flip a running product from very small to very large, so the best subarray is not always the one made only of positive numbers.

Examples

Input:  nums = [2,3,-2,4]
Output: 6
Why:    The subarray [2,3] gives product 6, which beats any subarray that includes the -2 or the 4 alone.

Input:  nums = [-2,0,-1]
Output: 0
Why:    Any subarray touching both negative numbers is blocked by the 0 in between, so the best achievable product is 0.

Input:  nums = [-2,3,-4]
Output: 24
Why:    Taking the whole array multiplies the two negatives into a positive, giving 24, which is larger than any shorter subarray.

Constraints

1 <= nums.length <= 2*10^4, -10 <= nums[i] <= 10

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Maximum Product Subarray

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Maximum Product Subarray. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.