Ends of the Row Duel
Problem
Two players face a row of cards with point values cards. They alternate turns, the first player starting. On each turn, the player removes either the leftmost or the rightmost card and adds its value to their score.
Both players play perfectly. Return the first player's final score minus the second player's final score.
Example 1
- Input:
- cards = [3, 9, 1, 2]
- Output:
- 7
The first player takes 2. Whatever the second player takes (3 or 1), the first player then grabs 9. Scores 11 and 4.
Example 2
- Input:
- cards = [5, 2, 4]
- Output:
- 3
Taking 5 leaves [2, 4]: the opponent takes 4 and the first player gets 2, so 7 against 4. Taking 4 first only reaches 6 against 5.
Constraints
- 1 ≤ cards.length ≤ 1000
- 0 ≤ cards[i] ≤ 10^6
Hint
Show the first hint
Whatever is left at any moment is a contiguous stretch cards[i..j]. Describe a position by (i, j).
Walkthrough
How to approach it
01Clarify before coding
- Is 'play perfectly' about maximising your own margin? Yes, each player maximises their score minus the other's, which is the same as maximising their own score since the total is fixed.
- Can the result be negative? With non-negative cards and the first move, it never is, but the recurrence does not depend on that.
- Is a single card possible? Yes, the first player simply takes it.
02Brute force
Explore the full game tree: at each turn try both ends and recurse.
Cost: O(2^n): the tree has a branch per turn, about 10^301 leaves for n = 1000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.