Maximize array sum after K negations | Set 2 | A PriorityQueue based C ++ program to maximize array sum after k negations . ; Function to find Maximum sum after K negations ; Create a min heap for priority queue ; Insert all elements in f array in priority_queue ; Retrieve and remove min element ; Modify the minimum element and add back to priority queue ; Calculate the sum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxSum ( int a [ ] , int n , int k ) { int sum = 0 ; priority_queue < int , vector < int > , greater < int > > pq ; for ( int i = 0 ; i < n ; i ++ ) { pq . push ( a [ i ] ) ; } while ( k -- ) { int temp = pq . top ( ) ; pq . pop ( ) ; temp = ( temp ) * -1 ; pq . push ( temp ) ; } while ( ! pq . empty ( ) ) { sum = sum + pq . top ( ) ; pq . pop ( ) ; } return sum ; } int main ( ) { int a [ ] = { -2 , 0 , 5 , -1 , 2 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 4 ; cout << MaxSum ( a , n , k ) ; return 0 ; }