#AT12. Deque

Deque

[L] Deque(dp_l)

来源: AtCoder Educational DP Contest - Problem L 原题时限:2 秒 / 内存:1024 MB

题目描述

太郎与次郎用长度为 NN 的数列 aa 玩游戏。

初始时,数列 aa 被放在一张桌子上。两人轮流进行如下操作,太郎先手:

  • 从数列的开头或末尾取走一个元素。取出者获得该元素的数值作为得分。

设最终太郎的总得分为 XX,次郎的总得分为 YY。太郎希望最大化 X−YX - Y,次郎希望最小化 X−YX - Y。

假设两人都采取最优策略,求最终 X−YX - Y 的值。

输入格式

输入由标准输入按以下格式给出:

N
a_1 a_2 \ldots a_N

输出格式

输出两人均采取最优策略时 X−YX - Y 的值。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤30001 \le N \le 3000
  • 1≤ai≤1091 \le a_i \le 10^9

样例 1

输入:

4
10 80 90 30

输出:

10

样例 2

输入:

3
10 100 10

输出:

-80

样例 3

输入:

1
10

输出:

10

样例 4

输入:

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

输出:

4999999995

样例 5

输入:

6
4 2 9 7 1 5

输出:

2