Maximize cost to empty an array by removing contiguous subarrays of equal elements | Initialize dp array ; Function that removes elements from array to maximize the cost ; Base case ; Check if an answer is stored ; Deleting count + 1 i . e . including the first element and starting a new sequence ; Removing [ left + 1 , i - 1 ] elements to continue with previous sequence ; Store the result ; Return answer ; Function to remove the elements ; Function call ; Given array ; Function call
let dp = new Array ( 101 ) ; for ( let i = 0 ; i < 101 ; i ++ ) { dp [ i ] = new Array ( 101 ) ; for ( let j = 0 ; j < 101 ; j ++ ) { dp [ i ] [ j ] = new Array ( 101 ) ; for ( let k = 0 ; k < 101 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } function helper ( arr , left , right , count , m ) { if ( left > right ) return 0 ; if ( dp [ left ] [ right ] [ count ] != - 1 ) { return dp [ left ] [ right ] [ count ] ; } let ans = ( count + 1 ) * m + helper ( arr , left + 1 , right , 0 , m ) ; for ( let i = left + 1 ; i <= right ; ++ i ) { if ( arr [ i ] == arr [ left ] ) { ans = Math . max ( ans , helper ( arr , left + 1 , i - 1 , 0 , m ) + helper ( arr , i , right , count + 1 , m ) ) ; } } dp [ left ] [ right ] [ count ] = ans ; return ans ; } function maxPoints ( arr , n , m ) { let len = arr . length ; return helper ( arr , 0 , len - 1 , 0 , m ) ; } let arr = [ 1 , 3 , 2 , 2 , 2 , 3 , 4 , 3 , 1 ] ; let M = 3 ; let N = arr . length ; document . write ( maxPoints ( arr , N , M ) ) ;