Minimum deletions in Array to make difference of adjacent elements non | C # 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 ; Initializing the dp table and setting all values to 0 ; Find the maximum size valid set that can be taken and then subtract its size from N to get minimum number of deletions ; When selecting only current element and deleting all elements from 0 to i - 1 inclusive ; If this is true moving from index j to i is possible ; Iterate over all elements from 0 to diff and find the max ; Take the max set size from dp [ N - 1 ] [ 0 ] to dp [ N - 1 ] [ MAX ] ; Driver Code ; Function call
using System ; class GFG { static int MAX = 100001 ; static int minimumDeletions ( int [ ] A , int N ) { int [ , ] dp = new int [ N , MAX ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < MAX ; j ++ ) dp [ 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 ] ; for ( int k = 0 ; k <= diff ; k ++ ) { dp [ i , diff ] = Math . Max ( dp [ i , diff ] , dp [ j , k ] + 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 ( ) { int [ ] A = { 1 , 4 , 5 , 7 , 20 , 21 } ; int N = A . Length ; Console . Write ( minimumDeletions ( A , N ) ) ; } }