Optimal Card Game Strategy

Alice and Bob are playing a card game with a row of cards, where each card has a positive integer value. In each turn, a player selects either the leftmost or the rightmost card from the row. Both players play optimally in order to maximize their own scores. Your task is to determine the maximum score that Alice can achieve if she starts the game.

The optimal strategy involves dynamic programming. In particular, let \(dp[i][j]\) denote the maximum score a player can secure from the subarray of cards from index \(i\) to \(j\). Then the recurrence relation is given by:

[ dp[i][j] = \max \Biggl( a_i + \min\bigl(dp[i+2][j], dp[i+1][j-1]\bigr),\quad a_j + \min\bigl(dp[i+1][j-1], dp[i][j-2]\bigr) \Biggr) ]

where \(a_i\) and \(a_j\) are the card values at positions \(i\) and \(j\) respectively. When only one card is available, the player takes that card. Use these ideas to compute the maximum score that Alice can secure.

inputFormat

The input is given in two lines:

• The first line contains a single integer \(n\) representing the number of cards.
• The second line contains \(n\) space-separated integers indicating the values of the cards.

outputFormat

Output a single integer representing the maximum score that Alice can achieve.

4
1 2 9 4

10