Coin Game
A row of coins is laid out, and you and a friend take turns removing one coin from either the left end or the right end of the row. You go first, and both of you play perfectly, meaning each always plays to maximise your own final total.
Return the highest score you can guarantee for yourself.
Input & Output
Input
coins — the values of the coins, in a row
Output
your maximum possible score when you move first and your friend plays perfectly
Example
Input
coins = [8, 15, 3, 7]
Output
22
Explanation
Take the 7 from the right. Your friend takes the 8, you take the 15, and your friend is left with the 3, so you score 7 + 15 = 22.
Taking the larger end first — the 8 — would leave you with only 15.
Example
Input
coins = [2, 2, 2, 2]
Output
4
Explanation
Every coin is worth the same, so however the game goes the four coins split two and two. You take two coins worth 2 each.
Constraints
1 <= len(coins) <= 10000 <= coins[i] <= 10^4