题目描述

给定一个包含 $n$ 个整数的数组 $a$。你需要对该数组依次执行以下两个操作（先执行第一个操作，再执行第二个操作）：

1. 可以任意重新排列数组中的元素，或者保持原有顺序不变。
2. 可以选择至多一个连续的元素区间，并将该区间内所有元素的符号取反。形式化地说，你可以选择一对下标 $l, r$，满足 $1 \le l \le r \le n$，然后对所有 $l \le i \le r$ 的 $a_i$ 执行 $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$），表示数组 $a$ 的元素。

输出格式

对于每个测试用例，输出依次执行上述两个操作后，数组元素和的最大值。

说明/提示

在第一个测试用例中，你可以先将数组重新排列为 $[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）。

由 ChatGPT 4.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

8
0
1
99
22
15
270
78