Maximize sum after K negations
Submissions: 3508   Accuracy:


  Difficulty: Easy   Marks: 2

Given an array of integers of size N and a number K. Your must modify array K number of times. Here modify array means in each operation you can replace any array element either arr[i] by -arr[i] or -arr[i] by arr[i]. You need to perform this operation in such a way that after K operations, sum of array must be maximum.

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines . The first line of each test case contains an integer N and K. The second line of each test case contains N space separated integers denoting elements of the array.

For each test case, print maximum possible sum.

1 ≤ T ≤ 100
1 ≤ N ≤ 107

-1018 ≤ Ai ≤ 1018

5 1
1 2 -3 4 5
10 5
5 -2 5 -4 5 -12 5 5 5 20


Testcase 1: 
In testcase 1 we have k=1 so we can change -3 to 3 and sum all the elements to produce 15 as output.
Testcase 2: Here  we have k=5 so we turn -2, -4, -12 to 2, 4, and 12 respectively. Since we have performed 3 operations so k is now 2. To get maximum sum of array we can turn positive turned 2 into negative and then positive again so k is 0. Now sum is 5+5+4+5+12+5+5+5+20+2 = 68


Author: kartik



to report an issue on this page.