Last Updated: 13 Feb, 2021
Max Sum After 'K' Negations
Easy
Asked in companies
You are given an array/list ‘arr’ of size ‘N’. Find the maximum sum of the elements of the array you can obtain after flipping the sign of exactly ‘K’ elements
For example :
Let arr = [-2, 0, 5, -1, 2]
and K = 4
We will output 10 as we replace -2 by 2, -1 by 1, 0 by 0, and 0 by 0.
Note :
We can apply the flip operation to the same element multiple times
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains ‘N’ denoting the number of elements in arr.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of ‘arr’
The third line of each test case contains an integer ‘K’ which denotes the number of flips to be done.
Output Format :
For each test case, return an integer which is the largest sum after ‘K’ flips.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N <= 5000
-10^6 <= arr[i] <=10^6
1 <= K <= N
Time limit: 1 second
Approaches
The key idea in solving this problem is that it is only beneficial to flip only the negative numbers to maximize our sum. Also, we can flip the positive numbers twice to again get a positive number.
We can find the negative numbers one by one as follows:
- We take a loop K times and in each iteration, traverse the loop and find the minimum element of the loop.
- If the minimum element is negative we make it positive by flipping its sign.
- If the minimum element is 0 we just terminate the loop
- If the minimum element is positive and k is odd, we flip the element and break the loop otherwise if even, we don't flip and break immediately.
- Finally, we calculate the sum of the array elements after the flips.
The key idea in solving this problem is to realize that we can simply sort the array to find the first ‘K’ elements
The algorithm will be -
- Sort the array using any of the traditional methods of sorting.
- Once sorted, Iterate through the array for the first ‘K’ elements and if the current element is negative, flip the sign.
- If zero, just break the loop.
- If positive, if ‘K’ is odd, flip the smallest positive number and break the loop, otherwise break immediately.
- Finally, calculate the sum of the elements of the modified array and return it.
Similar problems