Perform K of Q queries to maximize the sum of the array elements | 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
def getFinalSum ( a , n , queries , q , k ) : NEW_LINE INDENT answer = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT answer += a [ i ] NEW_LINE DEDENT contribution = [ ] NEW_LINE for i in range ( q ) : NEW_LINE INDENT contribution . append ( queries [ i ] [ 1 ] - queries [ i ] [ 0 ] + 1 ) NEW_LINE DEDENT contribution . sort ( reverse = True ) NEW_LINE i = 0 NEW_LINE while ( i < k ) : NEW_LINE INDENT answer += contribution [ i ] NEW_LINE i += 1 NEW_LINE DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 1 , 1 , 2 , 2 , 2 , 3 ] NEW_LINE n = len ( a ) NEW_LINE queries = [ [ 0 , 4 ] , [ 1 , 2 ] , [ 2 , 5 ] , [ 2 , 3 ] , [ 2 , 4 ] ] NEW_LINE q = len ( queries ) ; NEW_LINE k = 3 NEW_LINE print ( getFinalSum ( a , n , queries , q , k ) ) NEW_LINE DEDENT