Sum maximization game#5865
cards are laid out in a row from left to right. Each card has an integer written on it. Two players take turns picking up one card at a time. On each turn, a player may choose only the leftmost or the rightmost card remaining in the row. The game ends when all the cards have been taken (as long as there are cards, a player must make one of the available moves). The objective is to obtain the largest possible sum of integers from the cards taken by the player.
What maximum sum can the first player guarantee to collect, regardless of how the second player plays?
The first line contains the number of cards (1 \le N \le 2013). The second line contains integers, each not exceeding 10^3 in absolute value, representing the values written on the cards.
Output a single integer — the maximum sum the first player can guarantee to collect.
Example 1
If, on the first turn, the first player takes , the opponent must take either or . In either case, the first player will be able to take , so a sum of is guaranteed (after which the second player takes the last card and the game ends).
If, on the first move, the first player takes , the second player can respond by taking , leaving the first player with a maximum total of 3 + 2 = 5. Of course, if the second player responds unwisely by taking instead, then the first player could obtain 3 + 9 = 12. However, the first player cannot guarantee that the second player will make this mistake, so the answer is not but .