SP18297 CODEM4 - Problem4

"Roadies" 再次来袭！在印度，"Roadies" 是一档炙手可热的真人秀节目，深受年轻人喜爱。 为了加入 "Roadies"，节目组给你设置了一个挑战：设想你手中有一个由偶数个整数组成的数组。玩家 1 和玩家 2 轮流从数组中拿取数字，每次只能从数组的最左边或最右边选择一个。你的任务是找出玩家 1 所能获得的最大得分（所选数字之和），这里假设玩家 1 先开始游戏，并且每一步都做出最优选择。 **注意**：每当一个数字被选中后，它便从数组中移除。 然而，由于 "Roadies" 的传统风格，这里有个小变化。我们不知道第二个玩家是无脑选择还是深思熟虑。显然，玩家 2 的选择策略不同，结果也会不同。 特别说明，当玩家 2 像傻瓜一样玩时，他可能没有策略性的思考，总是随意从数组的开头或结尾拿数字。因此，玩家 1 的得分不唯一。 **你的任务是找出玩家 1 在玩家 2 无脑选择和聪明选择时的最大可能得分。**

第一行输入一个整数 $T$，表示测试用例的数量 $(T < 20)$。每组测试用例的第一行是一个整数 $N$，表示数组的长度。第二行给出 $N$ 个整数，表示数组的元素。

对于每个测试用例，输出两行。第一行输出当玩家 2 无脑选择时玩家 1 的最大可能得分。第二行输出当玩家 2 聪明选择时玩家 1 的最大可能得分。

$$1 \le T < 20, \quad 2 \le N \le 10^3, \quad -10^4 \le 数组中的元素 \le 10^4$$ **本翻译由 AI 自动生成**