解题思路

为什么可以把后手的目标变成：最大化自己的得分？

设数组为 $arr$ ，所有数的和为 $sum(arr)$ 。两人得分加起来是一个固定值：

score(先)+score(后)=sum(arr)

题目内容

给定正整数数组 $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分析」