Maximize cost to empty an array by removing contiguous subarrays of equal elements | Java 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
import java . util . * ; 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 ; System . out . print ( maxPoints ( arr , N , M ) ) ; } }