Arcade Tile Run
An arcade has a floor game: a long strip of light-up tiles, each showing a score. Some scores are bonuses, like +4, and some are traps, like -5. You jump onto any tile you like, run forward across the tiles one by one, and jump off whenever you choose. Your score is the sum of every tile you touched.
You can see all the tiles before you start. If you pick the best place to jump on and off, what score do you get?
Your task
Write bestRun(tiles). Return the largest possible sum of a run of one or more consecutive tiles.
You must touch at least one tile, so if every tile is negative the answer is the least negative tile, not 0. Return only the score, not the positions.
bestRun(tiles: int[]) → int
Examples
tiles = [3, -5, 4, -1, 6, -8, 2]
9
Jump on at the 4 and off after the 6: 4 - 1 + 6 = 9. Starting earlier at the 3 adds 3 - 5 = -2, which only hurts. Running on past the 6 hits the -8, and the 2 after it does not make up for it.
tiles = [-4, -2, -7]
-2
Every tile is a trap, but you must land on at least one. The best you can do is the single tile -2.
Constraints
- 1 ≤ tiles.length ≤ 100,000
- -10,000 ≤ tiles[i] ≤ 10,000
Start with brute force
Try every start and every end, and add up the tiles between them. With running sums that is about n²/2 runs to check.
For 100,000 tiles that is around 5 billion runs. The waste is that the run from 2 to 9 and the run from 3 to 9 share almost everything, yet each is treated as a brand-new question.
Hints
0 of 4 shown- Hint 1
Say you are standing on the 4 in
[3, -5, 4, -1, 6, -8, 2]and want the best run that ends right here. Would you want to bring along the tiles before it, which add up to 3 - 5 = -2? - Hint 2
A run that ends at a tile either starts fresh at that tile, or extends the best run that ended at the tile before. Extend only if that earlier run has a positive total; a negative total only drags you down.
- Hint 3
So for each tile:
endingHere = max(tile, endingHere + tile). The answer is the largestendingHereyou ever see, because the best run must end somewhere. - Hint 4
Walk once from left to right with two numbers: the best run ending at the current tile, and the best seen anywhere so far. Start both at the first tile (not 0), so an all-negative strip still gives the right answer.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Ask a smaller question at every tile: what is the best run that ends exactly here? It is either this tile alone or this tile added to the best run ending one tile earlier. The overall answer is the biggest of these.
Trace [3, -5, 4, -1, 6, -8, 2]:
- 3: endingHere = 3, best = 3.
- -5: max(-5, 3 - 5) = -2. best stays 3.
- 4: max(4, -2 + 4) = 4. Starting fresh wins, because the run behind us was negative.
- -1: max(-1, 4 - 1) = 3. best stays 4.
- 6: max(6, 3 + 6) = 9. best = 9.
- -8: max(-8, 9 - 8) = 1. best stays 9.
- 2: max(2, 1 + 2) = 3. best stays 9. Answer 9.
Starting at the first tile rather than at 0 is what makes [-4, -2, -7] return -2. If you start best at 0 you are quietly allowing an empty run.
function bestRun(tiles) {
let endingHere = tiles[0]; // best run that ends on the current tile
let best = tiles[0]; // best run seen anywhere so far
for (let i = 1; i < tiles.length; i++) {
// extend the previous run, or start fresh on this tile
endingHere = Math.max(tiles[i], endingHere + tiles[i]);
best = Math.max(best, endingHere);
}
return best;
}def best_run(tiles):
ending_here = tiles[0] # best run that ends on the current tile
best = tiles[0] # best run seen anywhere so far
for t in tiles[1:]:
# extend the previous run, or start fresh on this tile
ending_here = max(t, ending_here + t)
best = max(best, ending_here)
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.