Tutorialspoint.dev

Maximize array sum after K negations | Set 2

Given an array of size n and a number k. We must modify array K number of times. Here modify array means in each operation we can replace any array element arr[i] by -arr[i]. We need to perform this operation in such a way that after K operations, sum of array must be maximum?

Examples:

Input : arr[] = {-2, 0, 5, -1, 2} 
        K = 4
Output: 10
// Replace (-2) by -(-2), array becomes {2, 0, 5, -1, 2}
// Replace (-1) by -(-1), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}

Input : arr[] = {9, 8, 8, 5} 
        K = 3
Output: 20

We have discussed a O(nk) solution in below post.

Maximize array sum after K negations | Set 1

The idea used in above post is to replace the minimum element arr[i] in array by -arr[i] for current operation. In this way we can make sum of array maximum after K operations. Once interesting case is, once minimum element becomes 0, we don’t need to make any more changes.



The implementation used in above solution uses linear search to find minimum element. The time complexity of the above discussed solution is O(nk)

In this post an optimized solution is implemented that uses a priority queue (or binary heap) to find minimum element quickly.

Below is Java implementation of the idea. It uses PriorityQueue class in Java.

// A PriorityQueue based Java program to maximize array
// sum after k negations.
import java.util.*;
  
class maximizeSum
{
    public static int maxSum(int[] a, int k)
    {
        // Create a priority queue and insert all array elements
        // int
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : a)
            pq.add(x);
  
        // Do k negations by removing a minimum element k times
        while (k-- > 0)
        {
            // Retrieve and remove min element
            int temp = pq.poll();
  
            // Modify the minimum element and add back
            // to priority queue
            temp *= -1;
            pq.add(temp);
        }
  
        // Compute sum of all elements in priority queue.
        int sum = 0;
        for (int x : pq)
            sum += x;
        return sum;
    }
  
    // Driver code
    public static void main (String[] args)
    {
        int[] arr = {-2, 0, 5, -1, 2};
        int k = 4;
        System.out.println(maxSum(arr, k));
    }
}

Output:

10

Another Approach:(Efficient approach)

// A Java program to maximize array
// sum after k negations.
public class MaximizeSum {
  
// function to maximize array
// sum after k negations.
static void maxSumAfterNegation(int[] a,int k){
          
        int minPos = Integer.MAX_VALUE, sum = 0, index = -1;
          
        for(int i = 0; i < a.length; i++){
              
            // Do k negations by removing a minimum element k times
            if(k < 0){
                break;
            }
              
            if(a[i] < 0){
                a[i]=-a[i];
                k--;
            }
              
            if(a[i] < minPos && a[i] > -1){
                minPos = a[i];
                index = i;
            }
                // Compute sum of all elements
            sum+=a[i];
        }
          
        for(int i = k; i > 0; i--){
            a[index]=-a[index];
        }
          
        /*for(int i:a){
            sum+=i;
        }*/
          
        sum+=(2*a[index]);
          
        System.out.print(sum);
    }
      
    //Driver code
    public static void main(String[] args) {
        // TODO Auto-generated method stub
  
        int[] a= {-2, 0, 5, -1, 2} ;
            MaximizeSum.maxSumAfterNegation(a, 4);
      
    }
  
}

Output:

10

Note that this optimized solution can be implemented in O(n + kLogn) time as we can create a priority queue (or binary heap) in O(n) time.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter