/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
太郎君と次郎君が次のゲームで勝負します。
最初に、数列 a = (a_1, a_2, \ldots, a_N) が与えられます。 a が空になるまで、二人は次の操作を交互に行います。 先手は太郎君です。
- a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。
ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 太郎君は X - Y を最大化しようとし、次郎君は X - Y を最小化しようとします。
二人が最適に行動すると仮定したとき、X - Y を求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 3000
- 1 \leq a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \ldots a_N
出力
二人が最適に行動すると仮定したとき、X - Y を出力せよ。
入力例 1
4 10 80 90 30
出力例 1
10
二人が最適に行動すると、次のように操作が行われます。 操作対象の要素を太字で表しています。
- 先手: (10, 80, 90, 30) → (10, 80, 90)
- 後手: (10, 80, 90) → (10, 80)
- 先手: (10, 80) → (10)
- 後手: (10) → ()
このとき、X = 30 + 80 = 110, Y = 90 + 10 = 100 となります。
入力例 2
3 10 100 10
出力例 2
-80
二人が最適に行動すると、例えば次のように操作が行われます。
- 先手: (10, 100, 10) → (100, 10)
- 後手: (100, 10) → (10)
- 先手: (10) → ()
このとき、X = 10 + 10 = 20, Y = 100 となります。
入力例 3
1 10
出力例 3
10
入力例 4
10 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
出力例 4
4999999995
答えは 32-bit 整数型に収まらない場合があります。
入力例 5
6 4 2 9 7 1 5
出力例 5
2
二人が最適に行動すると、例えば次のように操作が行われます。
- 先手: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)
- 後手: (4, 2, 9, 7, 1) → (2, 9, 7, 1)
- 先手: (2, 9, 7, 1) → (2, 9, 7)
- 後手: (2, 9, 7) → (2, 9)
- 先手: (2, 9) → (2)
- 後手: (2) → ()
このとき、X = 5 + 1 + 9 = 15, Y = 4 + 7 + 2 = 13 となります。
Score : 100 points
Problem Statement
Taro and Jiro will play the following game against each other.
Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N). Until a becomes empty, the two players perform the following operation alternately, starting from Taro:
- Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.
Let X and Y be Taro's and Jiro's total score at the end of the game, respectively. Taro tries to maximize X - Y, while Jiro tries to minimize X - Y.
Assuming that the two players play optimally, find the resulting value of X - Y.
Constraints
- All values in input are integers.
- 1 \leq N \leq 3000
- 1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \ldots a_N
Output
Print the resulting value of X - Y, assuming that the two players play optimally.
Sample Input 1
4 10 80 90 30
Sample Output 1
10
The game proceeds as follows when the two players play optimally (the element being removed is written bold):
- Taro: (10, 80, 90, 30) → (10, 80, 90)
- Jiro: (10, 80, 90) → (10, 80)
- Taro: (10, 80) → (10)
- Jiro: (10) → ()
Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100.
Sample Input 2
3 10 100 10
Sample Output 2
-80
The game proceeds, for example, as follows when the two players play optimally:
- Taro: (10, 100, 10) → (100, 10)
- Jiro: (100, 10) → (10)
- Taro: (10) → ()
Here, X = 10 + 10 = 20 and Y = 100.
Sample Input 3
1 10
Sample Output 3
10
Sample Input 4
10 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
Sample Output 4
4999999995
The answer may not fit into a 32-bit integer type.
Sample Input 5
6 4 2 9 7 1 5
Sample Output 5
2
The game proceeds, for example, as follows when the two players play optimally:
- Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)
- Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)
- Taro: (2, 9, 7, 1) → (2, 9, 7)
- Jiro: (2, 9, 7) → (2, 9)
- Taro: (2, 9) → (2)
- Jiro: (2) → ()
Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13.