todo.txt (1464B)
1 swap-and-negate: 2 3 E. Swap and Negate 4 time limit per test 2 seconds 5 memory limit per test 256 megabytes 6 7 You are given an array a of length n. 8 9 You are allowed to perform the following operation on the array a any number of times (including zero): 10 11 Choose an index i such that 1≤i<n; 12 Set a_i:=−a_{i+1} and a_{i+1}:=−a_i simultaneously. 13 14 Determine the maximum possible sum of all elements in the array that can be achieved by performing the operations optimally. 15 Input 16 17 The first line of the input contains a single integer t (1≤t≤10^4) — the number of test cases. The description of each test case follows. 18 19 The first line of each test case contains a single integer n (1≤n≤2⋅10^5) — the length of the array a. 20 21 The second line of each test case contains n integers a1,a2,…,an (−10^9≤ai≤10^9) — the elements of the array a. 22 23 It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5. 24 Output 25 26 For each test case, print a single integer — the maximum possible sum of the array elements after performing the operations any number of times. 27 Example 28 Input 29 Copy 30 31 4 32 1 33 -3 34 4 35 1 -2 -3 4 36 5 37 -10 1 0 1 -10 38 2 39 6 -7 40 41 Output 42 Copy 43 44 -3 45 10 46 18 47 1 48 49 Note 50 51 For the first test case, no operation can be performed. Hence, the maximum sum will be equal to −3. 52 53 For the second test case, choosing i=2 makes the array a=[1,3,2,4]. Now, the sum of all the elements is equal to 10. It can be shown that this is the maximum possible.