Largest product of a run

mediumGreedy choiceDynamic programming, 1D target 25 min

Largest product of a run

Not solved yetLeetCode 152. Maximum Product Subarray

A run, also called a subarray, is one or more neighboring items of a list, in order, with no gaps. Multiply the items of a run together and you get its product: the run [3, -1, 2] has the product 3 × -1 × 2 = -6.

You get a list of integers nums. Return the largest product of any of its runs. A run holds at least one item, so [-5] gives -5, not 1 or 0.

Example 1

Inputnums = [-2, 3, -4, 0, 5]Output24

The run [-2, 3, -4] multiplies to 24: its two negatives cancel. Any run that reaches the 5 from the left holds the 0, so its product is 0.

Example 2

Inputnums = [3, -1, 4]Output4

Every run that holds the -1 has a negative product. Of the others, [4] beats [3].

Example 3

Inputnums = [-2, -3, -4]Output12

The run [-3, -4] multiplies to 12. The whole list holds three negatives, so its product, -24, is negative, and [-2, -3] gives only 6.

Constraints

1 ≤ len(nums) ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
The product of every run is between -2³¹ and 2³¹ - 1.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern