Maximum Product SubarrayMedium

Maximum Product Subarray

Medium 19.1k35% acceptance

ArrayDynamic Programming

Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest product, and return that product.

Negative values can flip a small product into a large one, so you must track both extremes as you sweep.

Example 1

Input: nums = [2,3,-2,4]

Output: 6

The subarray [2,3] has product 6; the -2 would drag any longer prefix negative.

Example 2

Input: nums = [-2,3,-4]

Output: 24

The whole array multiplies to (-2)·3·(-4) = 24 — two negatives make a positive.

Constraints

1 ≤ nums.length ≤ 2·10⁴
-10 ≤ nums[i] ≤ 10
The answer fits in a 32-bit integer.

Asked atAmazonLinkedInMicrosoftGoogle

JavaScript

⌘↵ to run

Loading editor…

Case 1

[2,3,-2,4]

expected: 6

Case 2

[-2,0,-1]

expected: 0

Case 3

[-2,3,-4]

expected: 24

Case 4

[2,-5,-2,-4,3]

expected: 24

Case 5

[-2]

expected: -2

Case 6

[0,2]

expected: 2