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 ; Driver Code ; Given array ; Function Call
dp = [ [ [ - 1 for x in range ( 101 ) ] for y in range ( 101 ) ] for z in range ( 101 ) ] NEW_LINE def helper ( arr , left , right , count , m ) : NEW_LINE INDENT if ( left > right ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ left ] [ right ] [ count ] != - 1 ) : NEW_LINE INDENT return dp [ left ] [ right ] [ count ] NEW_LINE DEDENT ans = ( ( count + 1 ) * m + helper ( arr , left + 1 , right , 0 , m ) ) NEW_LINE for i in range ( left + 1 , right + 1 ) : NEW_LINE INDENT if ( arr [ i ] == arr [ left ] ) : NEW_LINE ans = ( max ( ans , helper ( arr , left + 1 , i - 1 , 0 , m ) + helper ( arr , i , right , count + 1 , m ) ) ) NEW_LINE dp [ left ] [ right ] [ count ] = ans NEW_LINE return ans NEW_LINE DEDENT DEDENT def maxPoints ( arr , n , m ) : NEW_LINE INDENT length = n NEW_LINE global dp NEW_LINE return helper ( arr , 0 , length - 1 , 0 , m ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 2 , 2 , 3 , 4 , 3 , 1 ] NEW_LINE M = 3 NEW_LINE N = len ( arr ) NEW_LINE print ( maxPoints ( arr , N , M ) ) NEW_LINE DEDENT