P1430 Taking Numbers from a Sequence

Given an integer sequence of length $n$ $(n \le 1000)$, A and B take numbers in turns (A goes first). On each turn, a player may take one or more numbers from either the left end or the right end of the sequence, but not from both ends in the same turn. After all numbers have been taken, each player sums the numbers they took as their score. Assume A and B are both clever enough to play optimally and maximize their own score. Find A's final score.

The first line contains a positive integer $T$, indicating there are $T$ testcases $(T \le 100)$. Then follow $T$ lines. In each line, the first number is $n$, followed by $n$ integers that form the given sequence.

Output $T$ lines, each containing one integer, which is A's score.

Translated by ChatGPT 5