小鸿给你一个由 n 个元素组成的数组a，同时，你可以进行以下操作：
选择2个相邻的元素，翻转它们的符号。换句话说，选择一个索引i (1≤i≤n-1)，并使得 ai = -ai , ai+1 = -ai+1。
小鸿想知道该数组在执行任意次数的操作后可能具有的最大和，你能帮帮他吗？
2852: 正数与负数（思维）
时间限制: 2 Sec 内存限制: 256 MB提交: 0 解决: 4
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入由多个测试案例组成。第一行包含一个整数 t ( 1≤t≤1000 ) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 n ( 2 ≤n≤ 2⋅105) - 数组的长度。
下面一行包含n个空间分隔的整数 a1 ,a2 ,...,an( -109 ≤ai ≤109) 。
可以保证所有测试案例的 n 之和不超过 2x105。
每个测试用例的第一行包含一个整数 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。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版