[USACO10DEC] Treasure Chest S

题目描述

小 A 和小 B 在玩游戏。

初始时，有 $n$ 个硬币被摆成了一行，从左至右数第 $i$ 个硬币的价值为 $c_i$。

小 A 和小 B 每人一回合，在一个人的回合中，他可以选择当前硬币序列最左侧或者最右侧的硬币，并将他从序列中取出，将其价值累加到自己获得的累计价值中，然后进行另一个人的回合。当硬币全部被取走时，游戏结束。

请求出在双方都尽可能的使自己累计价值最大的情况下，若由小 A 进行第一回合，那么他能获得的累计价值最大是多少。

输入格式

输入的第一行是一个整数 $n$，代表硬币的个数。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

输出格式

输出一行一个整数，代表小 A 能获得的最大累计价值。

样例 #1

样例输入 #1

4 
30 
25 
10 
35

样例输出 #1

60

提示

输入输出样例 $1$ 解释

初始时，硬币序列为 \{30,~25,~10,~35\}。

第一回合，小 A 取走最右侧的硬币，序列变为 \{30,~25,~10\}，小 A 的累加价值为 $35$。

第二回合，小 B 取走最左侧的硬币，序列变为 \{25,~10\}，小 B 的累加价值为 $30$。

第三回合，小 A 取走最左侧的硬币，序列变为 $\{10\}$，小 A 的累加价值为 $35 + 25 = 60$。

第四回合，小 B 取走最左侧的硬币，序列变为空，小 B 的累加价值为 $30 + 10 = 40$，游戏结束。

小 A 获得的最大累计价值为 $60$。

数据范围与约定

对于全部的测试点，$1 \leq n \leq 5 \times 10^3$，$1 \leq c_i \leq 5 \times 10^3$。

提示：请注意，本题的空间限制为 $64$ Mib。