题目描述

给定一个包含 $n$ 个元素的数组 $a$，你可以进行如下操作任意次：

• 选择 $2$ 个相邻的元素，并将它们的符号都翻转。也就是说，选择一个下标 $i$，满足 $1 \leq i \leq n-1$，然后令 $a_i = -a_i$ 且 $a_{i+1} = -a_{i+1}$。

请你求出经过任意次上述操作后，数组可能获得的最大和。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot10^5$），表示数组的长度。

接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$）。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例，输出经过任意次操作后数组可能获得的最大和。

样例

5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1

1
13
6
39
2

样例说明

对于第一个测试用例，通过对前两个元素进行操作，可以将数组从 $[-1, -1, -1]$ 变为 $[1, 1, -1]$，可以证明这个数组获得的最大和为 $1 + 1 + (-1) = 1$。

对于第二个测试用例，通过对 $-5$ 和 $0$ 进行操作，可以将数组从 $[1, 5, -5, 0, 2]$ 变为 $[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$，此时所有元素都非负，和最大，为 $1 + 5 + 5 + 0 + 2 = 13$。

对于第三个测试用例，数组已经全为正数，无需操作，答案就是整个数组的和，即 $1 + 2 + 3 = 6$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1791E，英文题名 Negatives and Positives。