Maximize cost to empty an array by removing contiguous subarrays of equal elements | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 101 ] [ 101 ] [ 101 ] ; int helper ( int arr [ ] , int left , int right , int count , int m ) { if ( left > right ) return 0 ; if ( dp [ left ] [ right ] [ count ] != -1 ) { return dp [ left ] [ right ] [ count ] ; } int ans = ( count + 1 ) * m + helper ( arr , left + 1 , right , 0 , m ) ; for ( int i = left + 1 ; i <= right ; ++ i ) { if ( arr [ i ] == arr [ left ] ) { ans = max ( ans , helper ( arr , left + 1 , i - 1 , 0 , m ) + helper ( arr , i , right , count + 1 , m ) ) ; } } dp [ left ] [ right ] [ count ] = ans ; return ans ; } int maxPoints ( int arr [ ] , int n , int m ) { int len = n ; memset ( dp , -1 , sizeof ( dp ) ) ; return helper ( arr , 0 , len - 1 , 0 , m ) ; } int main ( ) { int arr [ ] = { 1 , 3 , 2 , 2 , 2 , 3 , 4 , 3 , 1 } ; int M = 3 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxPoints ( arr , N , M ) ; return 0 ; }