← 返回题目列表

Codeforces · 1791/E

E. 消极和积极

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

给定一个由 $$$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$$$。

输出

对于每个测试用例,输出在执行所描述的操作任意次后数组可以拥有的最大可能总和。

示例

输入 #1

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

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$$$。