Optimal Coin Game

Alice and Bob are playing an optimal coin game. A row of coins is placed on the table and each coin has a certain value. The players take turns picking a coin from either end of the row. Both players play optimally and try to maximize the amount of money they collect.

Given a list of coin values, compute the maximum amount of money that Alice (the first player) can guarantee to win.

The game can be modeled using dynamic programming. Let \(dp[i][j]\) represent the maximum amount of money the current player can secure from the subarray of coins starting at index \(i\) and ending at index \(j\). The recurrence is:

[ \begin{aligned} dp[i][j] &= \max\Bigl( coins[i] + \min(dp[i+2][j],; dp[i+1][j-1]), \[6pt] &\quad\quad coins[j] + \min(dp[i][j-2],; dp[i+1][j-1]) \Bigr) \ \end{aligned} ]

For a single coin, \(dp[i][i] = coins[i]\). The answer is \(dp[0][n-1]\) where \(n\) is the total number of coins.

inputFormat

The first line contains an integer \(n\) representing the number of coins.

The second line contains \(n\) space-separated integers, where each integer represents the value of a coin.

outputFormat

Output a single integer representing the maximum amount of money that Alice can collect, assuming both players play optimally.

4
1 2 9 4

10