Perform K of Q queries to maximize the sum of the array elements | Java implementation of the approach ; pair class ; Function to perform K queries out of Q to maximize the final sum ; Get the initial sum of the array ; Stores the contriution of every query ; comparator ; Sort the contribution of queries in descending order ; Get the K most contributions ; Driver code
import java . util . * ; class GFG { static class pair { int first , second ; pair ( int f , int s ) { first = f ; second = s ; } } static int getFinalSum ( int a [ ] , int n , pair queries [ ] , int q , int k ) { int answer = 0 ; for ( int i = 0 ; i < n ; i ++ ) answer += a [ i ] ; Vector < Integer > contribution = new Vector < Integer > ( ) ; for ( int i = 0 ; i < q ; i ++ ) { contribution . add ( queries [ i ] . second - queries [ i ] . first + 1 ) ; } Comparator < Integer > Comp = new Comparator < Integer > ( ) { public int compare ( Integer e1 , Integer e2 ) { if ( e1 > e2 ) return - 1 ; else return 1 ; } } ; Collections . sort ( contribution , Comp ) ; int i = 0 ; while ( i < k ) { answer += ( int ) contribution . get ( i ) ; i ++ ; } return answer ; } public static void main ( String args [ ] ) { int a [ ] = { 1 , 1 , 2 , 2 , 2 , 3 } ; int n = a . length ; pair queries [ ] = new pair [ 5 ] ; queries [ 0 ] = new pair ( 0 , 4 ) ; queries [ 1 ] = new pair ( 1 , 2 ) ; queries [ 2 ] = new pair ( 2 , 5 ) ; queries [ 3 ] = new pair ( 2 , 3 ) ; queries [ 4 ] = new pair ( 2 , 4 ) ; int q = queries . length ; int k = 3 ; System . out . println ( getFinalSum ( a , n , queries , q , k ) ) ; } }