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
< ? php function lis ( $ arr , $ n ) { $ result = 0 ; $ lis [ $ n ] = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ lis [ $ i ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] > $ arr [ $ j ] && $ lis [ $ i ] < $ lis [ $ j ] + 1 ) $ lis [ $ i ] = $ lis [ $ j ] + 1 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ result < $ lis [ $ i ] ) $ result = $ lis [ $ i ] ; return $ result ; } function minimumNumberOfDeletions ( $ arr , $ n ) { $ len = lis ( $ arr , $ n ) ; return ( $ n - $ len ) ; } $ arr = array ( 30 , 40 , 2 , 5 , 1 , 7 , 45 , 50 , 8 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo " Minimum ▁ number ▁ of ▁ deletions ▁ = ▁ " , minimumNumberOfDeletions ( $ arr , $ n ) ; ? >