← 返回题目列表

Codeforces · 1933/A

A. 海龟拼图:重新排列和否定

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您必须对数组执行以下两个操作(第一个,然后第二个):

1. 任意重新排列数组的元素或保持其元素的顺序不变。
2. 最多选择一个连续的元素段,并将该段中所有元素的符号替换为其相反数。形式上,您可以选择一对索引 $$$l, r$$$,使得 $$$1 \le l \le r \le n$$$ 并为所有 $$$l \le i \le r$$$ (否定元素)分配 $$$a_i = -a_i$$$。请注意,您可以选择不选择一对索引并保持元素的所有符号不变。

执行这两个操作(第一个,然后第二个)后数组元素的最大和是多少?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — 数组的元素。

输出

对于每个测试用例,依次执行两个给定操作后输出数组元素的最大和。

示例

输入 #1

8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12

输出 #1

8
0
1
99
22
15
270
78

注意

在第一个测试用例中,您可以先重新排列数组以获得$$$[3,-2,-3]$$$(操作1),然后选择$$$l = 2, r = 3$$$并获得总和$$$3 + -((-2) + (-3)) = 8$$$(操作2)。

在第二个测试用例中,您可以在这两个操作中不执行任何操作并获得总和 $$$0$$$。

在第三个测试用例中,您可以在这两个操作中执行任何操作,并得到总和 $$$0 + 1 = 1$$$。

在第四个测试用例中,您可以先保持顺序不变(操作 1),然后选择 $$$l = 1, r = 1$$$ 并得到总和 $$$-(-99) = 99$$$(操作 2)。

在第五个测试用例中,可以先保持顺序不变(操作 1),然后选择 $$$l = 2, r = 3$$$ 并得到总和 $$$10 + -((-2) + (-3)) + 7 = 22$$$(操作 2)。

在第六个测试用例中,可以先保持顺序不变(操作 1),然后选择 $$$l = 1, r = 5$$$ 并得到总和 $$$-((-1)+(-2)+(-3)+(-4)+(-5))=15$$$(操作 2)。