Maximum score assigned to a subsequence of numerically consecutive and distinct array elements | Java program for the above approach ; Function to find the maximum score possible ; Base Case ; If previously occurred subproblem occurred ; Check if lastpicked element differs by 1 from the current element ; Calculate score by including the current element ; Calculate score by excluding the current element ; Return maximum score from the two possibilities ; Function to print maximum score ; DP array to store results ; Initialise dp with - 1 ; Function call ; Driver Code ; Given arrays ; Function Call
import java . util . * ; class GFG { public static int maximumSum ( int [ ] a , int [ ] b , int n , int index , int lastpicked , int [ ] [ ] dp ) { if ( index == n ) return 0 ; if ( dp [ index ] [ lastpicked + 1 ] != - 1 ) return dp [ index ] [ lastpicked + 1 ] ; int option1 = 0 , option2 = 0 ; if ( lastpicked == - 1 a [ lastpicked ] != a [ index ] ) { option1 = b [ index ] + maximumSum ( a , b , n , index + 1 , index , dp ) ; } option2 = maximumSum ( a , b , n , index + 1 , lastpicked , dp ) ; return dp [ index ] [ lastpicked + 1 ] = Math . max ( option1 , option2 ) ; } public static void maximumPoints ( int arr [ ] , int brr [ ] , int n ) { int index = 0 , lastPicked = - 1 ; int dp [ ] [ ] = new int [ n + 5 ] [ n + 5 ] ; for ( int i [ ] : dp ) Arrays . fill ( i , - 1 ) ; System . out . println ( maximumSum ( arr , brr , n , index , lastPicked , dp ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 3 , 3 , 1 } ; int brr [ ] = { - 1 , 2 , 10 , 20 , - 10 , - 9 } ; int N = arr . length ; maximumPoints ( arr , brr , N ) ; } }