FunctionRacerProblemsRace

Coins From Either End

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

coins [3,9,1,2]
returns 7

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

coins [-4,1,-2]
returns -7

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems