Optimal Card Game Strategy

Nathan and his opponent are playing a strategic card game. A row of cards is laid out on the table, each with an integer value. In each turn, a player picks either the leftmost or rightmost card. Both players play optimally in order to maximize their own total score. Nathan always starts first.

Your task is to determine the maximum sum of card values Nathan can collect when he starts first, assuming both players play optimally.

The decision process can be modeled using dynamic programming. Let \(dp[i][j]\) represent the maximum sum Nathan can obtain from the subarray of cards from index \(i\) to \(j\). The recurrence relation is given by:

[ dp[i][j] = \max \Bigl( cards[i] + \min\left(dp[i+2][j],; dp[i+1][j-1]\right),; cards[j] + \min\left(dp[i+1][j-1],; dp[i][j-2]\right) \Bigr) ]

with the base case \(dp[i][i] = cards[i]\) when there is only one card left.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) representing the number of cards. The second line contains \(n\) space-separated integers representing the values on the cards.

outputFormat

The output is a single integer printed to standard output (stdout), which represents the maximum sum Nathan can obtain by playing first under optimal play.

## sample

4
1 2 9 4

10

</p>