Perform K of Q queries to maximize the sum of the array elements | C ++ implementation of the approach ; 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 ; Sort the contribution of queries in descending order ; Get the K most contributions ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getFinalSum ( int a [ ] , int n , pair < int , int > queries [ ] , int q , int k ) { int answer = 0 ; for ( int i = 0 ; i < n ; i ++ ) answer += a [ i ] ; vector < int > contribution ; for ( int i = 0 ; i < q ; i ++ ) { contribution . push_back ( queries [ i ] . second - queries [ i ] . first + 1 ) ; } sort ( contribution . begin ( ) , contribution . end ( ) , greater < int > ( ) ) ; int i = 0 ; while ( i < k ) { answer += contribution [ i ] ; i ++ ; } return answer ; } int main ( ) { int a [ ] = { 1 , 1 , 2 , 2 , 2 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; pair < int , int > queries [ ] = { { 0 , 4 } , { 1 , 2 } , { 2 , 5 } , { 2 , 3 } , { 2 , 4 } } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; int k = 3 ; cout << getFinalSum ( a , n , queries , q , k ) ; return 0 ; }