45. 虚拟棋盘对战（第五期模拟笔试）
内存限制：128 MB
时间限制：1.000 S
题目描述
两个玩家在一款虚拟棋盘游戏中对战，棋盘上有一行格子，长度为 n，每个格子上都有不同的分数。玩家 A 和玩家 B 轮流选择一个格子，他们都希望最终获得的总分数更高。规则是，每个玩家可以选择棋盘上的任何一端的格子，然后将该格子上的分数加入自己的总分。游戏结束后，获得最高总分的玩家获胜。
两位玩家都非常聪明，他们会采用最优策略来选择格子以最大化自己的得分。
输入
第一行为一个正整数 n
第二行为 n 个正整数
输出
输出一个整数，为两个玩家中的最高分
样例输入 复制
4
10 40 60 20样例输出 复制
70提示
当 A 先选的时候，在最外层的 10 和 20 之间选择 10 了以后，无论 B 怎么选择，60 必定落到 A 手里。所以 A 能拿到70分，B 再聪明也只能拿到60分。