/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君と青木君が、カードを使ったゲームで対戦します。
テーブルの上に N 枚のカードが一列に並んでおり、左から i 番目のカードには整数 A_i が書かれています。
高橋君を先手として、二人は交互に以下の操作を行います。
- テーブルに残っているカードのうち、左端のカードまたは右端のカードのどちらか一方を選んで取り除く。取り除いたカードは捨てられ、以降のゲームには一切影響しない。
テーブルにカードがちょうど 1 枚だけ残った時点でゲームは終了します（すなわち、操作は合計 N - 1 回行われます）。最後に残った 1 枚のカードに書かれた整数を、このゲームのスコアとします。
高橋君はスコアをできるだけ大きくしたいと考えており、青木君はスコアをできるだけ小さくしたいと考えています。二人がともにそれぞれの目的に対して最適に行動したとき、ゲームのスコアを求めてください。
なお、N = 1 の場合は操作が一度も行われず、最初からある 1 枚のカードに書かれた整数がそのままスコアとなります。
制約
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
N A_1 A_2 \ldots A_N
- 1 行目には、カードの枚数を表す整数 N が与えられる。
- 2 行目には、各カードに書かれた整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
二人がともに最適に行動したとき、ゲームのスコアを 1 行で出力せよ。
入力例 1
3 1 5 2
出力例 1
2
入力例 2
4 7 -3 10 1
出力例 2
10
入力例 3
10 4 -8 15 16 -23 42 0 7 -5 9
出力例 3
42
入力例 4
30 12 -45 78 0 -999 34 56 -12 300 17 -88 91 5 -6 123 -321 44 55 -66 77 88 -99 1000 -1000 3 2 1 -1 -2 -3
出力例 4
123
入力例 5
1 -1000000000
出力例 5
-1000000000
Score : 400 pts
Problem Statement
Takahashi and Aoki are playing a game using cards.
There are N cards arranged in a row on the table, and the i-th card from the left has an integer A_i written on it.
With Takahashi going first, the two players alternately perform the following operation:
- Choose either the leftmost card or the rightmost card among the cards remaining on the table, and remove it. The removed card is discarded and has no further effect on the game.
The game ends when exactly 1 card remains on the table (that is, a total of N - 1 operations are performed). The integer written on the last remaining card is the score of this game.
Takahashi wants to maximize the score, and Aoki wants to minimize the score. Determine the score of the game when both players act optimally toward their respective goals.
Note that when N = 1, no operations are performed, and the integer written on the single card that is already there becomes the score as is.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- All inputs are integers.
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of cards.
- The second line contains the integers A_1, A_2, \ldots, A_N written on each card, separated by spaces.
Output
Print the score of the game in one line when both players act optimally.
Sample Input 1
3 1 5 2
Sample Output 1
2
Sample Input 2
4 7 -3 10 1
Sample Output 2
10
Sample Input 3
10 4 -8 15 16 -23 42 0 7 -5 9
Sample Output 3
42
Sample Input 4
30 12 -45 78 0 -999 34 56 -12 300 17 -88 91 5 -6 123 -321 44 55 -66 77 88 -99 1000 -1000 3 2 1 -1 -2 -3
Sample Output 4
123
Sample Input 5
1 -1000000000
Sample Output 5
-1000000000