Minimum number of deletions to make a sorted sequence | lis ( ) returns the length of the longest increasing subsequence in arr [ ] of size n ; Initialize LIS values for all indexes ; Compute optimized LIS values in bottom up manner ; Pick resultimum of all LIS values ; function to calculate minimum number of deletions ; Find longest increasing subsequence ; After removing elements other than the lis , we get sorted sequence . ; Driver Code
function lis ( arr , n ) { let result = 0 ; let lis = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) lis [ i ] = 1 ; for ( let i = 1 ; i < n ; i ++ ) for ( let j = 0 ; j < i ; j ++ ) if ( arr [ i ] > arr [ j ] && lis [ i ] < lis [ j ] + 1 ) lis [ i ] = lis [ j ] + 1 ; for ( let i = 0 ; i < n ; i ++ ) if ( result < lis [ i ] ) result = lis [ i ] ; return result ; } function minimumNumberOfDeletions ( arr , n ) { let len = lis ( arr , n ) ; return ( n - len ) ; } let arr = [ 30 , 40 , 2 , 5 , 1 , 7 , 45 , 50 , 8 ] ; let n = arr . length ; document . write ( " " + minimumNumberOfDeletions ( arr , n ) ) ;