#P1430. 序列取数

序列取数

题目描述

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

输入格式

第一行,一个正整数 TT,表示有 TT 组数据。(T100T \le 100

接着 TT 行,每行第一个数为 nn,接着 nn 个整数表示给定的序列。

输出格式

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

2
1 -1
2 1 2
-1
3