Minimum deletions in Array to make difference of adjacent elements non | 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
var MAX = 100001 ; function minimumDeletions ( A , N ) { var dp = new Array ( N , MAX ) ; var pref = new Array ( N , MAX ) ; for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < MAX ; j ++ ) { dp [ i , j ] = 0 ; pref [ i , j ] = 0 ; } } for ( var i = 0 ; i < N ; i ++ ) { dp [ i , 0 ] = 1 ; for ( var j = i - 1 ; j >= 0 ; j -- ) { if ( A [ i ] >= A [ j ] ) { var diff = A [ i ] - A [ j ] ; dp [ i ] = Math . max ( dp [ i , diff ] , pref [ j , diff ] + 1 ) ; } } pref [ i , 0 ] = dp [ i , 0 ] ; for ( var j = 1 ; j < MAX ; j ++ ) pref [ i , j ] = Math . max ( dp [ i , j ] , pref [ i , j - 1 ] ) ; } var maxSetSize = - 1 ; for ( var i = 0 ; i < MAX ; i ++ ) maxSetSize = Math . max ( maxSetSize , dp [ N - 1 , i ] ) ; return N - maxSetSize ; } var A = [ 1 , 4 , 5 , 7 , 20 , 21 ] ; var N = A . length ; document . write ( minimumDeletions ( A , N ) ) ;