Problem Description

Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins.

The N (1 <= N <= 5,000) coins, each with some value C_i (1 <= C_i <= 5,000) are placed in a straight line. Bessie and Bonnie take turns, and for each cow's turn, she takes exactly one coin off of either the left end or the right end of the line. The game ends when there are no coins left.

Bessie and Bonnie are each trying to get as much wealth as possible for themselves. Bessie goes first. Help her figure out the maximum value she can win, assuming that both cows play optimally.

Consider a game in which four coins are lined up with these values:

30 25 10 35

Consider this game sequence:

Bessie    Bonnie       New Coin

Player   Side   CoinValue   Total     Total         Line

Bessie   Right     35        35         0       30  25  10

Bonnie   Left      30        35        30         25  10

Bessie   Left      25        60        30           10

Bonnie   Right     10        60        40           --

This is the best game Bessie can play.

Two players, A and B, are playing a game.

Initially, there are $n$ coins in a line. From left to right, the value of the $i$-th coin is $c_i$.

A and B take turns, one move per turn. On a player's turn, they must choose the leftmost or the rightmost coin from the current sequence, remove it from the sequence, and add its value to their own total. The game ends when all coins have been taken.

Assuming both players play optimally to maximize their own total value, and player A moves first, determine the maximum total value that A can obtain.

Input Format

• The first line contains an integer $n$, the number of coins.
• Lines $2$ to $(n + 1)$ each contain one integer. The integer on line $(i + 1)$ is the value $c_i$ of the $i$-th coin.

Output Format

Output a single integer: the maximum total value that player A can obtain.

4 
30 
25 
10 
35 

60 

Hint

• Sample explanation:

  Initially, the coin sequence is $\{30,~25,~10,~35\}$.

  • Turn 1: A takes the rightmost coin, the sequence becomes $\{30,~25,~10\}$, and A’s total is $35$.
  • Turn 2: B takes the leftmost coin, the sequence becomes $\{25,~10\}$, and B’s total is $30$.
  • Turn 3: A takes the leftmost coin, the sequence becomes $\{10\}$, and A’s total is $35 + 25 = 60$.
  • Turn 4: B takes the leftmost coin, the sequence becomes empty, and B’s total is $30 + 10 = 40$. The game ends.

  The maximum total value that A can obtain is $60$.

• Constraints:

  For all testdata, $1 \leq n \leq 5 \times 10^3$, $1 \leq c_i \leq 5 \times 10^3$.

• Note: The memory limit is $64$ MiB.

Translated by ChatGPT 5