← 返回题目列表

Codeforces · 2062/C

C. 琪露诺与行动

中文机器翻译题面 查看原题

Cirno 有一个长度为 $$$n$$$ 的序列 $$$a$$$。她可以执行以下两个操作中的任何一个(可能是零次),除非 $$$a$$$ 的当前长度是 $$$1$$$:

- 反转顺序。形式上,$$$[a_1,a_2,\ldots,a_n]$$$ 在操作后变为 $$$[a_n,a_{n-1},\ldots,a_1]$$$。
- 将序列替换为其差异序列。形式上,$$$[a_1,a_2,\ldots,a_n]$$$ 在操作后变为 $$$[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$$$。

求 $$$a$$$ 经过所有操作后元素的最大可能总和。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 输入测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 50$$$) — 序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i|\le 1000$$$) — 序列 $$$a$$$。

输出

对于每个测试用例,打印一个表示最大可能总和的整数。

示例

输入 #1

5
1
-1000
2
5 -3
2
1000 1
9
9 7 9 -9 9 -8 7 -8 9
11
678 201 340 444 453 922 128 987 127 752 0

输出 #1

-1000
8
1001
2056
269891

注意

在第一个测试用例中,Cirno 无法执行任何操作,因此答案是 $$$-1000$$$。

在第二个测试用例中,琪露诺首先反转序列,然后用其差异序列替换该序列:$$$[5,-3]\to[-3,5]\to[8]$$$。可以证明这使得总和最大化,所以答案是$$$8$$$。

在第三个测试用例中,琪露诺可以选择不操作,所以答案是$$$1001$$$。