Coins From Either End
Coins lie in a row, and coins[i] is the value of coin i; a negative value is a debt. Two players take turns, the first player moving first. On every turn the player must take either the leftmost or the rightmost coin still in the row.
Both players play as well as possible, each trying to end with the largest total. Return the first player's total minus the second player's total once the row is empty. An empty row gives 0.
Example 1
Take the 2. Whichever end the second player takes, the 9 is then yours: 2 + 9 = 11 against 3 + 1 = 4. Starting with the 3 would hand over the 9.
Example 2
Either first move leaves the 1 at an end for the second player, so the first player is stuck with -4 and -2: -6 - 1 = -7.
Constraints
0 <= len(coins) <= 60-1000 <= coins[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Count DerangementsMedium
- Count the Free PlotsMedium
- Dice Sum WaysMedium
- Fairest Stone SplitMedium
- Fewest Perfect SquaresMedium
- Gems That ClashMedium
- Hands That Hit the TargetMedium
- Keystrokes to TransformMedium