Maximum Product Subarray in an Array

Hard

Track the smallest product too

Problem

Given an integer array nums. Find the subarray with the largest product, and return the product of the elements present in that subarray. A subarray is a contiguous non-empty sequence of elements within an array.

In simple words

Track the biggest AND smallest running product — a negative can flip the smallest into the biggest.

The idea

A negative number turns the smallest product into the largest, so carry both a running maximum and a running minimum and swap them when you meet a negative. A zero resets both to 1, starting a fresh segment.

The trick

Swap max and min before multiplying by a negative value.
A zero breaks the array into independent segments — restart from 1.
O(n) single pass, O(1) space.

←→stepspaceplay

-2

1/12

Brute force

timeO(n²)spaceO(1)

Multiply every subarray.

1// multiply out every subarray, keep the biggest2let best = -Infinity;3for (let i = 0; i < n; i++) {4  let p = 1;5  for (let j = i; j < n; j++) {6    p *= nums[j];7    best = Math.max(best, p);8  }9}

Input

array: [2, 3, -2, 4]

Output

best: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

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

Example 2

Input:: nums = [-2, 0, -1]
Output:: 0
Explanation:: The best you can do is 0.

Example 3

Input:: nums = [-2, 3, -4]
Output:: 24
Explanation:: Two negatives multiply into a big positive: -2*3*-4 = 24.

Constraints

1 <= nums.length <= 10^4
-10 <= nums[i] <= 10
-10^9 <= product of any prefix or suffix of nums <= 10^9

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.