Optimal Card Game Strategy

In this problem, two players, Alice and Bob, play a card game with a deck of n cards where each card has an associated value. Alice always goes first. In each turn, a player picks either the leftmost or the rightmost card from the deck. Both players play optimally, meaning they try to maximize their own score.

Your task is to compute the maximum sum of card values that Alice can achieve under optimal play.

The game's optimal strategy can be formulated using dynamic programming. Let \(dp[i][j]\) denote the maximum sum Alice can secure from the subarray \(cards[i...j]\). The recurrence is defined as follows:

$$ \begin{aligned} dp[i][j] &= \max\Bigl( cards[i] + \bigl(\text{sum}(cards[i+1 \dots j]) - dp[i+1][j]\bigr),\\ &\quad\quad\, cards[j] + \bigl(\text{sum}(cards[i \dots j-1]) - dp[i][j-1]\bigr)\Bigr) \end{aligned} $$

Here, \(\text{sum}(cards[a \dots b])\) denotes the sum of the card values from index \(a\) to \(b\). The answer is given by \(dp[0][n-1]\), which considers the entire deck.

Note that even though both players are playing optimally, Alice's result is calculated based on her initial move and the subsequent optimal responses.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains an integer \(n\) representing the number of cards.
• The second line contains \(n\) space-separated integers, each representing the value of a card.

outputFormat

Output a single integer to standard output (stdout) – the maximum sum of card values that Alice can obtain under optimal play.

## sample

4
1 2 9 4

10