Problem

Submissions

Hints & solutions

Discuss

Max Sum After 'K' Negations

Easy

0/40

Average time to solve is 15m

Contributed by

4 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4
9 8 8 5
3
6
1 2 9 -90 6 4
1

Sample Output 1:

20
112

Explanation For Sample Input 1 :

Test Case 1 :

In the first test case, we will flip 5 to make it -5 and then apply the flip operation twice to any of the numbers to obtain the array {9, 8, 8, -5} whose sum is 20 hence we return 20.

Test Case 2 :

In the second test case, we will flip -90 to 90 in the one operation we can do to get {1, 2, 9, 90, 6, 4} whose sum is 112. Hence we return 112.

Sample Input 2 :

Sample Output 2 :

2
8

Hint 1

Hint 2

Can we use some observation like if we flip a number two times we get the same number?

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(K * N), where ‘N’ is the length of arr and K is the number of flips needed to be done.

In each iteration, we find the minimum element which takes O(N) time, and in the worst case this will happen K times, hence the total time complexity is O(K * N).

Space Complexity

O(1)

We are using constant space.

(100% EXP penalty)

Max Sum After 'K' Negations

Console