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
using System ; class GFG { static int [ , , ] dp = new int [ 101 , 101 , 101 ] ; static 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 = 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 ; } static int maxPoints ( int [ ] arr , int n , int m ) { int len = n ; for ( int i = 0 ; i < 101 ; i ++ ) { for ( int j = 0 ; j < 101 ; j ++ ) { for ( int k = 0 ; k < 101 ; k ++ ) dp [ i , j , k ] = - 1 ; } } return helper ( arr , 0 , len - 1 , 0 , m ) ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 2 , 2 , 2 , 3 , 4 , 3 , 1 } ; int M = 3 ; int N = arr . Length ; Console . Write ( maxPoints ( arr , N , M ) ) ; } }