311093: CF1933A. Turtle Puzzle: Rearrange and Negate
Description
You are given an array $a$ of $n$ integers. You must perform the following two operations on the array (the first, then the second):
- Arbitrarily rearrange the elements of the array or leave the order of its elements unchanged.
- Choose at most one contiguous segment of elements and replace the signs of all elements in this segment with their opposites. Formally, you can choose a pair of indices $l, r$ such that $1 \le l \le r \le n$ and assign $a_i = -a_i$ for all $l \le i \le r$ (negate elements). Note that you may choose not to select a pair of indices and leave all the signs of the elements unchanged.
What is the maximum sum of the array elements after performing these two operations (the first, then the second)?
InputThe first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the number of elements in array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100 \le a_i \le 100$) — elements of the array.
OutputFor each test case, output the maximum sum of the array elements after sequentially performing the two given operations.
ExampleInput8 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 12Output
8 0 1 99 22 15 270 78Note
In the first test case, you can first rearrange the array to get $[3,-2,-3]$ (operation 1), then choose $l = 2, r = 3$ and get the sum $3 + -((-2) + (-3)) = 8$ (operation 2).
In the second test case, you can do nothing in both operations and get the sum $0$.
In the third test case, you can do nothing in both operations and get the sum $0 + 1 = 1$.
In the fourth test case, you can first leave the order unchanged (operation 1), then choose $l = 1, r = 1$ and get the sum $-(-99) = 99$ (operation 2).
In the fifth test case, you can first leave the order unchanged (operation 1), then choose $l = 2, r = 3$ and get the sum $10 + -((-2) + (-3)) + 7 = 22$ (operation 2).
In the sixth test case, you can first leave the order unchanged (operation 1), then choose $l = 1, r = 5$ and get the sum $-((-1)+(-2)+(-3)+(-4)+(-5))=15$ (operation 2).
Output
这个题目是关于“乌龟拼图：重排和取反”。给定一个包含n个整数的数组a，你需要对数组执行以下两个操作（先执行第一个，然后执行第二个）：
1. 随意重新排列数组的元素，或者保持元素的原顺序不变。
2. 选择至多一个连续的元素段，并把这个段中所有元素的符号改为它们的相反数。形式上，你可以选择一对索引l, r（1≤l≤r≤n），并对所有l≤i≤r的ai赋值为-ai（取反元素）。注意，你也可以选择不选任何索引对，保持所有元素符号不变。
问题是，执行这两个操作后（先执行第一个，然后执行第二个），数组的元素最大和是多少？
输入数据格式：
输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤50）——数组a中的元素数量。
每个测试用例的第二行包含n个整数a1, a2, …, an（-100≤ai≤100）——数组的元素。
输出数据格式：
对于每个测试用例，输出执行这两个给定操作后数组的元素最大和。
例：
输入
```
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
```
输出
```
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）。
- 以此类推。题目大意： 这个题目是关于“乌龟拼图：重排和取反”。给定一个包含n个整数的数组a，你需要对数组执行以下两个操作（先执行第一个，然后执行第二个）： 1. 随意重新排列数组的元素，或者保持元素的原顺序不变。 2. 选择至多一个连续的元素段，并把这个段中所有元素的符号改为它们的相反数。形式上，你可以选择一对索引l, r（1≤l≤r≤n），并对所有l≤i≤r的ai赋值为-ai（取反元素）。注意，你也可以选择不选任何索引对，保持所有元素符号不变。 问题是，执行这两个操作后（先执行第一个，然后执行第二个），数组的元素最大和是多少？ 输入数据格式： 输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤50）——数组a中的元素数量。 每个测试用例的第二行包含n个整数a1, a2, …, an（-100≤ai≤100）——数组的元素。 输出数据格式： 对于每个测试用例，输出执行这两个给定操作后数组的元素最大和。 例： 输入 ``` 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 ``` 输出 ``` 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）。 - 以此类推。