Maximum score possible from an array with jumps of at most length K | Python 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
import sys NEW_LINE def maxScore ( i , A , K , N , dp ) : NEW_LINE INDENT if ( i >= N - 1 ) : NEW_LINE INDENT return A [ N - 1 ] ; NEW_LINE DEDENT if ( dp [ i ] != - 1 ) : NEW_LINE INDENT return dp [ i ] ; NEW_LINE DEDENT score = 1 - sys . maxsize ; NEW_LINE for j in range ( 1 , K + 1 ) : NEW_LINE INDENT score = max ( score , maxScore ( i + j , A , K , N , dp ) ) ; NEW_LINE DEDENT dp [ i ] = score + A [ i ] ; NEW_LINE return dp [ i ] ; NEW_LINE DEDENT def getScore ( A , N , K ) : NEW_LINE INDENT dp = [ 0 ] * N ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT dp [ i ] = - 1 ; NEW_LINE DEDENT print ( maxScore ( 0 , A , K , N , dp ) ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 100 , - 30 , - 50 , - 15 , - 20 , - 30 ] ; NEW_LINE K = 3 ; NEW_LINE N = len ( A ) ; NEW_LINE getScore ( A , N , K ) ; NEW_LINE DEDENT