Maximize Array sum after changing sign of any elements for exactly M times | Java implementation of the above approach ; Function to find the maximum sum with M flips ; Declare a priority queue i . e . min heap ; Declare the sum as zero ; Push all elements of the array in it ; Iterate for M times ; Get the top element ; Flip the sign of the top element ; Remove the top element ; Update the sum ; Push the temp into the queue ; Driver Code ; Given input
import java . util . * ; import java . lang . * ; import java . lang . Math ; class GFG { static void findMaximumSumWithMflips ( int arr [ ] , int N , int M ) { PriorityQueue < Integer > minHeap = new PriorityQueue < Integer > ( ) ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { minHeap . add ( arr [ i ] ) ; sum += arr [ i ] ; } while ( M -- > 0 ) { sum -= minHeap . peek ( ) ; int temp = - 1 * minHeap . peek ( ) ; minHeap . remove ( ) ; sum += temp ; minHeap . add ( temp ) ; } System . out . println ( sum ) ; } public static void main ( String [ ] args ) { int arr [ ] = { - 3 , 7 , - 1 , - 5 , - 3 } ; int M = 4 , N = 5 ; findMaximumSumWithMflips ( arr , N , M ) ; } }