Maximum Product Subarray

The key idea

A subarray product can flip sign, so the largest product ending at i may come from the *smallest* (most negative) product ending at i-1 multiplied by a negative nums[i]. Track BOTH the running max and the running min at each index, and swap them when nums[i] is negative.

Problem

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

The test cases are generated so that the answer fits in a 32-bit integer. A subarray is a contiguous, non-empty run of elements within nums.

Constraints

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

Examples

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

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

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

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →