Stretch With the Largest Product

Medium

You get an integer array values. Choose a non-empty stretch of consecutive elements whose product is as large as possible and return that product. Keep in mind that values may be negative or zero.

Example 1

values=[-3, 2, -4, 0, 5] → 24

The stretch [-3, 2, -4] gives (-3) · 2 · (-4) = 24, since the two negatives cancel out. Past the zero the best is just 5.

Example 2

values=[-5, 0, -2] → 0

The stretches [-5, 0, -2] and [0] give 0, and -5 or -2 alone are worse. -5 and -2 are not adjacent, so they cannot be multiplied on their own.

Example 3

values=[-7] → -7

Constraints

1 ≤ len(values) ≤ 2·10⁴
-10 ≤ values[i] ≤ 10
The product of any stretch is at most 2³¹ in absolute value

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

values=[-3, 2, -4, 0, 5]

Expected

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.