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 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100001 NEW_LINE int minimumDeletions ( int A [ ] , int N ) { int dp [ N ] [ MAX ] ; int pref [ 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 ] = max ( dp [ i ] , pref [ j ] + 1 ) ; } } pref [ i ] [ 0 ] = dp [ i ] [ 0 ] ; for ( int j = 1 ; j < MAX ; j ++ ) pref [ i ] [ j ] = max ( dp [ i ] [ j ] , pref [ i ] [ j - 1 ] ) ; } int maxSetSize = -1 ; for ( int i = 0 ; i < MAX ; i ++ ) maxSetSize = max ( maxSetSize , dp [ N - 1 ] [ i ] ) ; return N - maxSetSize ; } int main ( ) { int A [ ] = { 1 , 4 , 5 , 7 , 20 , 21 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minimumDeletions ( A , N ) << endl ; return 0 ; }