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 ; 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 ] ; Input ; Function call
let MAX = 100001 function minimumDeletions ( A , N ) { let dp = new Array ( N ) . fill ( 0 ) . map ( ( ) => new Array ( MAX ) ) ; for ( let i = 0 ; i < N ; i ++ ) for ( let j = 0 ; j < MAX ; j ++ ) dp [ i ] [ j ] = 0 ; for ( let i = 0 ; i < N ; i ++ ) { dp [ i ] [ 0 ] = 1 ; for ( let j = i - 1 ; j >= 0 ; j -- ) { if ( A [ i ] >= A [ j ] ) { let diff = A [ i ] - A [ j ] ; for ( let k = 0 ; k <= diff ; k ++ ) { dp [ i ] = Math . max ( dp [ i ] , dp [ j ] [ k ] + 1 ) ; } } } } let maxSetSize = - 1 ; for ( let i = 0 ; i < MAX ; i ++ ) maxSetSize = Math . max ( maxSetSize , dp [ N - 1 ] [ i ] ) ; return N - maxSetSize ; } let A = [ 1 , 4 , 5 , 7 , 20 , 21 ] ; let N = A . length ; document . write ( minimumDeletions ( A , N ) + " " ) ;