Find the maximum product of a contiguous subarray
In a puzzle game, a row of tiles each carries an integer multiplier. On their final move, the player drags across one unbroken run of tiles, and their score is multiplied by the product of every tile in that run. A negative tile flips the sign, so two negative tiles cancel out, and a 0 tile wipes the score. The game shows a hint with the best multiplier the player could get.
Implement bestMultiplierRun(tiles). It returns the largest product of a non-empty contiguous run of tiles.
bestMultiplierRun(tiles) // => number | null
tiles.slice(i, j). Its value is the product of its tiles.null when tiles is empty.-10 to 10. Every product in the tests fits in a safe integer.tiles can hold up to 5,000 values. Trying every run is quadratic; aim for one pass.tiles.bestMultiplierRun([3, 2, -4, 5]); // => 6 (3 × 2)
bestMultiplierRun([-3, 2, -5]); // => 30 (all three: the negatives cancel)
bestMultiplierRun([-1, -2, -3]); // => 6 (-2 × -3)
bestMultiplierRun([-6, 0, -1]); // => 0 (the 0 tile on its own)
bestMultiplierRun([0, -3, 1, -2, 0, 4, 5]); // => 20 (4 × 5)
bestMultiplierRun([-7]); // => -7
bestMultiplierRun([]); // => null
A negative tile can turn the most negative product so far into the largest one. Track both the largest and the smallest product of a run that ends at the current tile.