Maximum sum game - controlled opponent#5866
There are cards laid out in a row from left to right. Each card contains an integer. Two players alternately take one card at a time. On each turn, a player may only take either the leftmost or rightmost card remaining in the row. The game ends when all cards have been taken (as long as there are cards left, the player must make a move). The objective of the game is to collect the largest possible sum of the integers written on the taken cards.
However, it is not clear why Boss-Tyrant and his Subordinate-Toady are playing this game. The Boss-Tyrant can completely control not only his own moves but also those of the Subordinate-Toady. What is the maximum sum the Boss-Tyrant (who, of course, moves first) can guarantee to collect in a single game?
The first line contains the number of cards (1 \leq N \leq 2013). The second line contains integers, with absolute values not exceeding 10^3, representing the integers written on the cards.
Output a single integer: the maximum sum that the Boss-Tyrant (the first player) can guarantee to collect.
Example 1
Since the Boss-Tyrant fully controls the Subordinate-Toady's moves, he can first take the card with , then order the opponent to take , pick , so he gets 3 + 9 = 12, after which the Subordinate-Toady takes , and so the "fairest" game ends.