405. The Largest Product of a Run
Print the largest product of any contiguous run of at least one element.
Problem #57 does this for SUMS, where one running value is enough: the best run ending here is either this element alone or this element added to the best run ending before it.
Products break that argument, and the reason is the whole problem. A negative number turns the largest product into the smallest and the smallest into the largest. So the best run ending here might extend the WORST run ending before it:
-2 3 -4 -> 24
The best run ending at -4 extends -2 3, whose product is -6, the worst
prefix available. Any solution tracking only the maximum reports 3.
So carry two values, not one:
newMax = max(v, maxSoFar * v, minSoFar * v)
newMin = min(v, maxSoFar * v, minSoFar * v)
Both must be computed from the OLD pair before either is overwritten, or the second line uses a value the first has already replaced.
Zero is worth checking by hand: it makes both running values 0, which correctly restarts the run at the next element.
Constraints - `1 ≤ n ≤ 20000` - `-10 ≤ a[i] ≤ 10` - The answer fits in a signed 64-bit integer.
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the largest product of any contiguous run of at least one element.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.