Maximum score assigned to a subsequence of numerically consecutive and distinct array elements | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSum ( int a [ ] , int b [ ] , int n , int index , int lastpicked , vector < vector < 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 ] = max ( option1 , option2 ) ; } void maximumPoints ( int arr [ ] , int brr [ ] , int n ) { int index = 0 , lastPicked = -1 ; vector < vector < int > > dp ( n + 5 , vector < int > ( n + 5 , -1 ) ) ; cout << maximumSum ( arr , brr , n , index , lastPicked , dp ) << endl ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 3 , 3 , 1 } ; int brr [ ] = { -1 , 2 , 10 , 20 , -10 , -9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maximumPoints ( arr , brr , N ) ; return 0 ; }