Coin Game

Coin Game

You and a friend are playing a game with n coins arranged in a straight line, where each coin has a distinct value given by coins[i]. Starting with you, both players take turns, picking one coin from either end of the line and adding its value to their individual scores. Once a coin is picked up, it's removed from the line.

Given that your friend plays optimally to achieve the highest score, determine your maximum possible score.

Input

• coins: A list of the coins.

Output

Your maximum possible score, provided that you go first and your friend plays perfectly.

Examples

Example 1:

Input:

coins = [4, 4, 9, 4]

Output: 13

Explanation:

The coins start like this:

4, 4, 9, 4

You always go first, so you take the 4 from the left side:

4, 9, 4

Your friend takes any of the 4s (it doesn't matter)

9, 4

Now you take the 9, and your friend takes the remaining 4.

Your score in this case, is 4 + 9 = 13.

Constraints

• 1 <= len(coins) <= 1000
• 1 <= coins[i] <= 5 * 10^5

Try it yourself

Solution