解题思路

两人轮流取当前区间的两端，总分固定，后手最小化先手得分等价于双方都最大化自己的得分。用区间 DP。

设 $dp[i][j]$ 表示轮到当前玩家时，从 $a[i..j]$ 能拿到的最大得分。
长度为 $1$ 时 $dp[i][i]=a[i]$ 。
区间和记为 $s$ 。取左端后对手在剩余区间得 $dp[i+1][j]$ ，取右端后对手得 $dp[i][j-1]$ 。当前得分等于 $s$ 减去对手得分，因此 $dp[i][j]=s-\min(dp[i+1][j],\ dp[i][j-1])$

题目内容

给定正整数数组 $a$ 。两人轮流从当前序列两端各取一个数，先手最大化自己的得分之和，后手最小化先手得分。双方均按最优策略取数，求先手的最终得分。

第一行一个整数 $n$ 。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ 。

输出一个整数，表示先手的最终得分。

输入：

4
3 9 1 2

输出：

说明：先手取右端 $2$ 后，无论后手取哪一端，先手都能再拿到 $9$ ，总分 $11$ 。若先手取左端 $3$ ，后手会取走 $9$ ，先手最多再得 $2$ ，总分 $5$ 。

输入：

1
5

输出：

选择提交后点击「开始AI分析」