Maximum score possible from an array with jumps of at most length K | C ++ program for the above approach ; Function to count the maximum score of an index ; Base Case ; If the value for the current index is pre - calculated ; Calculate maximum score for all the steps in the range from i + 1 to i + k ; Score for index ( i + j ) ; Update dp [ i ] and return the maximum value ; Function to get maximum score possible from the array A [ ] ; Array to store memoization ; Initialize dp [ ] with - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxScore ( int i , int A [ ] , int K , int N , int dp [ ] ) { if ( i >= N - 1 ) return A [ N - 1 ] ; if ( dp [ i ] != -1 ) return dp [ i ] ; int score = INT_MIN ; for ( int j = 1 ; j <= K ; j ++ ) { score = max ( score , maxScore ( i + j , A , K , N , dp ) ) ; } return dp [ i ] = score + A [ i ] ; } int getScore ( int A [ ] , int N , int K ) { int dp [ N ] ; for ( int i = 0 ; i < N ; i ++ ) dp [ i ] = -1 ; cout << maxScore ( 0 , A , K , N , dp ) ; } int main ( ) { int A [ ] = { 100 , -30 , -50 , -15 , -20 , -30 } ; int K = 3 ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; getScore ( A , N , K ) ; return 0 ; }