Removal Game

题目描述

有一个包含 $n$ 个数的列表，两个玩家轮流走子。每次走子时，玩家从列表中移除第一个或最后一个数，并且其得分增加该数。两位玩家都尽力使自己的得分最大化。 当双方都采用最优策略时，先手玩家的最大可能得分是多少？

输入格式

第一行输入包含一个整数 $n$：列表的大小。 下一行有 $n$ 个整数 $x_1,x_2,$$\ldots$$,x_n$：列表的内容。

输出格式

输出先手玩家的最大可能得分。

4
4 5 1 3

8

提示

$1 \le n \le 5000$ $-10^9 \le x_i \le 10^9$

标签: CSES1097|动态规划|DP

来源

CSES1097|动态规划|DP