Best product
The largest product of a run of numbers, negatives included. About 12 minutes.
Continue or start fresh, with a twist
"Best stretch" problems keep coming back to the same question: does the best stretch ending here continue the one before, or start fresh? With products there's a twist. A negative number flips signs: a big negative product can turn into a big positive one.
So ask: what do I need to remember about the stretches ending just before, if the next number might be negative?
- hi
- 2
- lo
- 2
- best
- 2
Keep two numbers for runs ending here: the biggest product and the smallest. A negative can flip the smallest into the biggest.
The smallest product of a stretch ending at the previous number is −12, and the next number is −2. What product can the stretch reach?
- A24
- B−2 at best
- COnly the previous largest product matters
Show the answer
24. −12 × −2 = 24. That's why the smallest product has to be remembered too.
Best product
You get a non-empty list of small whole numbers. Return the largest product of a non-empty run of consecutive numbers.
nums = [2, 3, -2, 4] → 6
1 ≤ n ≤ 15 · −10 ≤ each value ≤ 10 · products fit in a long