Maximum score possible after performing given operations on an Array | Memoizing by the use of a table ; Function to calculate maximum score ; Bse case ; If the same state has already been computed ; Sum of array in range ( l , r ) ; If the operation is even - numbered the score is decremented ; Exploring all paths , and storing maximum value in DP table to avoid further repetitive recursive calls ; Function to find the max score ; Prefix sum array ; Calculating prefix_sum ; Initialising the DP table , - 1 represents the subproblem hasn 't been solved yet ; Driver code
let dp = new Array ( 100 ) ; for ( let i = 0 ; i < 100 ; i ++ ) { dp [ i ] = new Array ( 100 ) ; for ( let j = 0 ; j < 100 ; j ++ ) { dp [ i ] [ j ] = new Array ( 100 ) ; for ( let k = 0 ; k < 100 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } function MaximumScoreDP ( l , r , prefix_sum , num ) { if ( l > r ) return 0 ; if ( dp [ l ] [ r ] [ num ] != - 1 ) return dp [ l ] [ r ] [ num ] ; let current_sum = prefix_sum [ r ] - ( l - 1 >= 0 ? prefix_sum [ l - 1 ] : 0 ) ; if ( num % 2 == 0 ) current_sum *= - 1 ; dp [ l ] [ r ] [ num ] = current_sum + Math . max ( MaximumScoreDP ( l + 1 , r , prefix_sum , num + 1 ) , MaximumScoreDP ( l , r - 1 , prefix_sum , num + 1 ) ) ; return dp [ l ] [ r ] [ num ] ; } function findMaxScore ( a , n ) { let prefix_sum = new Array ( n ) ; prefix_sum [ 0 ] = a [ 0 ] ; for ( let i = 1 ; i < n ; i ++ ) { prefix_sum [ i ] = prefix_sum [ i - 1 ] + a [ i ] ; } return MaximumScoreDP ( 0 , n - 1 , prefix_sum , 1 ) ; } let n = 6 ; let A = [ 1 , 2 , 3 , 4 , 2 , 6 ] ; document . write ( findMaxScore ( A , n ) ) ;