Maximize Array sum after changing sign of any elements for exactly M times | C ++ program for 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 program ; Given input
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findMaximumSumWithMflips ( int arr [ ] , int N , int M ) { priority_queue < int , vector < int > , greater < int > > pq ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { pq . push ( arr [ i ] ) ; sum += arr [ i ] ; } while ( M -- ) { sum -= pq . top ( ) ; int temp = -1 * pq . top ( ) ; pq . pop ( ) ; sum += temp ; pq . push ( temp ) ; } cout << sum ; } int main ( ) { int arr [ ] = { -3 , 7 , -1 , -5 , -3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = 4 ; findMaximumSumWithMflips ( arr , N , M ) ; return 0 ; }