MediumDynamic Programming · Arrays

Maximum Product Subarray

Given an integer array nums, return the largest product of a contiguous, non-empty subarray.

nums = [2,4,−3,5] → 8 ([2,4])nums = [−3,0,−2] → 0

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The array

Brackets below = subarrays being tracked; gold above = best so far

Time and space complexity

n = len(nums). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Integers from −10 to 10; drawings use at most 10 numbers for brute force and 14 for the others.