Maximum Product Subarray
Real-world version: Best Multiplier Tile RunThe statement here is our own: the same inputs, outputs and technique.
A board game deals out a row of scoring tiles. Tile i carries the whole number factors[i], which may be negative, zero or positive.
On your turn you pick one unbroken stretch of neighbouring tiles, hold at least one tile, and walk across the whole stretch. You enter with a score of 1 and your score is multiplied by each tile's number as you step onto it. Skipping a tile inside the stretch is not allowed.
Report the highest score any single stretch can leave you with.
Examples
Example 1
- Input
- factors = [3, -1, -4, 2]
- Output
- 24
Walking all four tiles pairs the two negative numbers off against each other, giving 3 * -1 * -4 * 2 = 24. Stopping earlier never gets past 12.
Example 2
- Input
- factors = [-7, 0, -5]
- Output
- 0
Both single negative tiles leave a negative score, so the best available stretch is one that steps on the zero tile.
Example 3
- Input
- factors = [-6]
- Output
- -6
A stretch has to hold at least one tile, so the only choice available scores -6.
Constraints
- 1 <= factors.length <= 2 * 10^4
- -10 <= factors[i] <= 10
- The score of any unbroken stretch of factors is guaranteed to fit in a signed 32-bit integer.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def best_tile_run(factors: list[int]) -> int:public int bestTileRun(int[] factors)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's