Minimum number of deletions to make a sorted sequence | Java implementation to find 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
class GFG { static int lis ( int arr [ ] , int n ) { int result = 0 ; int [ ] lis = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) lis [ i ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) for ( int j = 0 ; j < i ; j ++ ) if ( arr [ i ] > arr [ j ] && lis [ i ] < lis [ j ] + 1 ) lis [ i ] = lis [ j ] + 1 ; for ( int i = 0 ; i < n ; i ++ ) if ( result < lis [ i ] ) result = lis [ i ] ; return result ; } static int minimumNumberOfDeletions ( int arr [ ] , int n ) { int len = lis ( arr , n ) ; return ( n - len ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 30 , 40 , 2 , 5 , 1 , 7 , 45 , 50 , 8 } ; int n = arr . length ; System . out . println ( " Minimum ▁ number ▁ of " + " ▁ deletions ▁ = ▁ " + minimumNumberOfDeletions ( arr , n ) ) ; } }