CF729F Financiers Game

本题具有不寻常的内存限制。 傍晚时分，金融家 Igor 和 Zhenya 觉得无聊，于是他们决定玩一个游戏。他们准备了 $n$ 张纸条，每张上面写着某家公司在某个时间段的收入。注意，收入可以为正数、零或负数。 Igor 和 Zhenya 把纸条排成一行，并决定轮流行动。Igor 每次从左边取纸条，Zhenya 每次从右边取纸条。Igor 先手，他可以选择从左边拿走 $1$ 或 $2$ 张纸条。之后，每一回合，当前玩家可以从自己这一侧取走 $k$ 或 $k+1$ 张纸条，其中 $k$ 是对手上一次取的纸条数。如果上一次对手取了 $k$ 张，这一轮就只能取 $k$ 或 $k+1$ 张。玩家不能跳过自己的回合。当没有纸条可取或者某一方无法按照规则取纸条时，游戏结束。 请你计算，假设两人都采取最优策略，Igor 取到的收入总和减去 Zhenya 取到的收入总和的最大可能值。Igor 的目标是让这个差值最大，Zhenya 的目标是让差值最小。

第一行包含一个正整数 $n$（$1 \leq n \leq 4000$）——纸条的数量。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$-10^{5} \leq a_{i} \leq 10^{5}$），其中 $a_{i}$ 表示从左往右第 $i$ 张纸条上的收入。

输出一个整数，表示在双方最优策略下，Igor 取到的收入总和减去 Zhenya 取到的收入总和的最大可能值。Igor 的目标是最大化这个差值，Zhenya 的目标是最小化它。

在第一个样例中，Igor 最优的做法是从左边拿两张纸，总收入为 $4$。此时只剩下一张纸，Zhenya 需要拿 $2$ 或 $3$ 张，但无法满足，所以游戏结束。 由 ChatGPT 5 翻译