Minimum deletions in Array to make difference of adjacent elements non | Java program for the above approach ; the maximum value of A [ i ] ; Function for finding minimum deletions so that the array becomes non - decreasing and the difference between adjacent elements is also non - decreasing ; initialize the dp table and set all values to 0 pref [ i ] [ j ] will contain min ( dp [ i ] [ 0 ] , dp [ i ] [ 1 ] , ... dp [ i ] [ j ] ) ; find the maximum sized valid set possible and then subtract its size from N to get minimum number of deletions ; when selecting only the current element and deleting all elements from 0 to i - 1 inclusive ; if this is true , moving from index j to i is possible ; we can get min ( dp [ j ] [ 0 ] , . . dp [ j ] ) from pref array ; ; construct the prefix array for this element ; take the max set size from dp [ N - 1 ] [ 0 ] to dp [ N - 1 ] [ MAX ] ; Driver Code ; Function call
import java . io . * ; class GFG { static int MAX = 100001 ; static int minimumDeletions ( int A [ ] , int N ) { int [ ] [ ] dp = new int [ N ] [ MAX ] ; int [ ] [ ] pref = new int [ N ] [ MAX ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; pref [ i ] [ j ] = 0 ; } } for ( int i = 0 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = 1 ; for ( int j = i - 1 ; j >= 0 ; j -- ) { if ( A [ i ] >= A [ j ] ) { int diff = A [ i ] - A [ j ] ; dp [ i ] = Math . max ( dp [ i ] , pref [ j ] + 1 ) ; } } pref [ i ] [ 0 ] = dp [ i ] [ 0 ] ; for ( int j = 1 ; j < MAX ; j ++ ) pref [ i ] [ j ] = Math . max ( dp [ i ] [ j ] , pref [ i ] [ j - 1 ] ) ; } int maxSetSize = - 1 ; for ( int i = 0 ; i < MAX ; i ++ ) maxSetSize = Math . max ( maxSetSize , dp [ N - 1 ] [ i ] ) ; return N - maxSetSize ; } public static void main ( String [ ] args ) { int A [ ] = { 1 , 4 , 5 , 7 , 20 , 21 } ; int N = A . length ; System . out . println ( minimumDeletions ( A , N ) ) ; } }