#F. 序列取数

远端评测题

3000ms

125MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长为 $n$ 的整数序列 $(n \le 1000)$ ，由 A 和 B 轮流取数（A 先取）。每个人可从序列的左端或右端取若干个数（至少一个），但不能两端都取。所有数都被取走后，两人分别统计所取数的和作为各自的得分。假设 A 和 B 都足够聪明，都使自己得分尽量高，求 A 的最终得分。

第一行，一个正整数 $T$ ，表示有 $T$ 组数据。（ $T \le 100$ ）

接着 $T$ 行，每行第一个数为 $n$ ，接着 $n$ 个整数表示给定的序列。

输出T行，每行一个整数，表示 A 的得分。

2
1 -1
2 1 2

-1
3