Optimal Card Game Strategy

Harry and Sally are playing a card game. A row of cards is placed on the table, each with a positive integer value. Both players take turns picking one card from either end of the row. They both play optimally to maximize their own points.

The task is to calculate the maximum points that Harry can achieve if he moves first.

The solution uses dynamic programming to evaluate the optimal difference between the two players. In particular, the recurrence is given by:

$$dp[i][j] = \max\big( cards[i] - dp[i+1][j],\; cards[j] - dp[i][j-1]\big) $$

Once dp[0][n-1] is computed, Harry's final score is calculated as:

$$\text{Harry's Points} = \frac{\text{total sum} + dp[0][n-1]}{2} $$

Note that the division is integer division.

inputFormat

The first line contains an integer n representing the number of cards.

The second line contains n space-separated integers representing the values of the cards.

outputFormat

Output a single integer representing the maximum points that Harry can earn.

## sample

4
1 2 3 4

6