Maximum score possible from an array with jumps of at most length K | C ++ program for the above approach ; Structure to sort a priority queue on the basis of first element of the pair ; Function to calculate maximum score possible from the array A [ ] ; Stores the score of previous k indices ; Stores the maximum score for current index ; Maximum score at first index ; Traverse the array to calculate maximum score for all indices ; Remove maximum scores for indices less than i - K ; Calculate maximum score for current index ; Push maximum score of current index along with index in maxheap ; Return the maximum score ; Driver Code ; Function call to calculate maximum score from the array A [ ]
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct mycomp { bool operator() ( pair < int , int > p1 , pair < int , int > p2 ) { return p1 . first < p2 . first ; } } ; int maxScore ( int A [ ] , int K , int N ) { priority_queue < pair < int , int > , vector < pair < int , int > > , mycomp > maxheap ; int maxScore = 0 ; maxheap . push ( { A [ 0 ] , 0 } ) ; for ( int i = 1 ; i < N ; i ++ ) { while ( maxheap . top ( ) . second < ( i - K ) ) { maxheap . pop ( ) ; } maxScore = A [ i ] + maxheap . top ( ) . first ; maxheap . push ( { maxScore , i } ) ; } return maxScore ; } int main ( ) { int A [ ] = { -44 , -17 , -54 , 79 } ; int K = 2 ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << maxScore ( A , K , N ) ; return 0 ; }