Best Product Run

Medium1-D Dynamic Programming

Problem

A sequence of multipliers nums is applied to a signal. A run is one or more consecutive multipliers, and its gain is the product of its elements.

Return the largest gain of any run.

Example 1

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

The run [2, 3].

Example 2

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

The run [0]; [-2, -1] is not contiguous.

Example 3

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

The whole array: two negatives cancel.

Constraints

  • 1 ≤ nums.length ≤ 2·10^4
  • -10 ≤ nums[i] ≤ 10
  • The product of any run fits in a 32-bit signed integer.

Hint

Show the first hint

Try Kadane's idea: the best run ending at i. Why does keeping only the maximum fail here?

Walkthrough

How to approach it

01Clarify before coding

  • Must the run be non-empty? Yes, so [-2] answers -2.
  • Can there be zeros? Yes, and a zero resets every run that crosses it.
  • Overflow? Guaranteed to fit in 32 bits for any run.

02Brute force

For every start index, extend to the right multiplying as you go and keep the best product.

Cost: O(n²) time, O(1) space: 2·10^8 multiplications for n = 2·10^4, too slow.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.