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