Max Game Score: Maximize Score by Choosing Moves in a Turn-Based Score Game

Question

## Problem

You are playing a single-player game on a row of `n` tiles, each with a score value. On each turn you may move 1, 2, or 3 tiles forward and collect that tile's score. You start before tile 0. Find the maximum total score achievable when you reach or pass tile `n-1`.

```python
def max_game_score(tiles: list[int]) -> int:
    pass
```

**Example:**
```
tiles = [1, -2, 3, -1, 4]
-> 8   # jump: 0->2->4: scores 3+4=7, or 0->1->2->4: 1+(-2)+3+4=6
        # or 0->2->3->4: 3+(-1)+4=6. Best: 0->2->4=7? Wait try 0->1->4: 1+(-2)[skip]->4: 1+4=5
        # Actually 0->2->4: collect tile[2]=3 + tile[4]=4 = 7. Check: is 8 achievable?
        # Recalculate: can land on tile 0 (score=1), skip, tile2 (3), skip, tile4 (4) = 1+3+4=8? No: start before 0.
        # Start -> tile[0]=1 -> tile[2]=3 -> tile[4]=4 => 1+3+4=8. Yes.
-> 8
```

## Follow-ups

1. Formulate the recurrence relation. What is the time and space complexity?
2. How do you optimize space from O(n) to O(1) since each state only depends on the previous 3?
3. What changes if negative-score tiles cannot be skipped (must land on every tile)?
4. How would you extend this to a 2D grid where you can move right or down 1-3 steps?

Max Game Score: Maximize Score by Choosing Moves in a Turn-Based Score Game

Question Details

Full Details

Topics

More from Uber