Coins in a Line

Leetcode article

EPI 17.9

Description:

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Would you rather go first or second? Does it matter? Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

Hints: If you go first, is there a strategy you can follow which prevents you from losing? Try to consider how it matters when the number of coins are odd vs. even.

https://articles.leetcode.com/coins-in-line/

Example:

{25, 5, 10, 5, 10, 5, 10, 25, 1, 25, 1, 25, 1, 25, 5, 10}

Idea:

Code:

Code