algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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.