Maximum possible Array sum after performing given operations | Java implementation to find the maximum possible sum of array after performing given operations ; Function to get maximum sum after q operations ; priority queue to get maximum sum ; Push pair , value and 1 in the priority queue ; Push pair , value ( to be replaced ) and number of elements ( to be replaced ) ; Add top n elements from the priority queue to get max sum ; pr is the pair pr . first is the value and pr . second is the occurrence ; pop from the priority queue ; Add value to answer ; Update n ; Driver Code
import java . util . * ; import java . lang . * ; class GFG { static class pair { int first , second ; pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void max_sum ( int ar [ ] , int n , int q , int x [ ] , int y [ ] ) { int ans = 0 , i ; PriorityQueue < pair > pq = new PriorityQueue < > ( ( a , b ) -> Integer . compare ( a . second , b . second ) ) ; for ( i = 0 ; i < n ; i ++ ) pq . add ( new pair ( ar [ i ] , 1 ) ) ; for ( i = 0 ; i < q ; i ++ ) pq . add ( new pair ( y [ i ] , x [ i ] ) ) ; while ( n > 0 ) { pair pr = pq . peek ( ) ; pq . poll ( ) ; ans += pr . first * Math . min ( n , pr . second ) ; n -= pr . second ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int ar [ ] = { 200 , 100 , 200 , 300 } ; int n = ar . length ; int q = 2 ; int x [ ] = { 2 , 3 } ; int y [ ] = { 100 , 90 } ; max_sum ( ar , n , q , x , y ) ; } }