Maximum score possible from an array with jumps of at most length K | JAVA 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 java . io . * ; import java . math . * ; import java . util . * ; public class GFG { static 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 = Integer . MIN_VALUE ; for ( int j = 1 ; j <= K ; j ++ ) { score = Math . max ( score , maxScore ( i + j , A , K , N , dp ) ) ; } return dp [ i ] = score + A [ i ] ; } static void getScore ( int A [ ] , int N , int K ) { int dp [ ] = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) dp [ i ] = - 1 ; System . out . println ( maxScore ( 0 , A , K , N , dp ) ) ; } public static void main ( String args [ ] ) { int A [ ] = { 100 , - 30 , - 50 , - 15 , - 20 , - 30 } ; int K = 3 ; int N = A . length ; getScore ( A , N , K ) ; } }