Responsive image

问题 2852 --正数与负数（思维）

2852: 正数与负数（思维）

时间限制: 2 Sec  内存限制: 256 MB
提交: 0  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

小鸿给你一个由 n 个元素组成的数组a，同时，你可以进行以下操作：

选择2个相邻的元素，翻转它们的符号。换句话说，选择一个索引i (1≤i≤n-1)，并使得 ai = -ai , ai+1 = -ai+1。

小鸿想知道该数组在执行任意次数的操作后可能具有的最大和，你能帮帮他吗？

输入描述

输入由多个测试案例组成。第一行包含一个整数 t ( 1≤t≤1000 ) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 n ( 2 ≤n≤ 2⋅105) - 数组的长度。

下面一行包含n个空间分隔的整数 a1 ,a2 ,...,an( -109 ≤ai ≤109) 。

可以保证所有测试案例的 n 之和不超过 2x105。

输出描述

对于每个测试案例，在执行描述的操作任意次数后，输出数组可能具有的最大和。

样例输入

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=13。

对于第三个测试案例，数组已经只包含正数，所以没有必要进行运算。答案只是整个数组的总和，即1+2+3=6。

来源

22计一张德鸿CF849(div4).E (1100分)  

[提交][状态]
ACM算法攻关部