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
def lis ( arr , n ) : NEW_LINE INDENT result = 0 NEW_LINE lis = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT lis [ i ] = 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] and lis [ i ] < lis [ j ] + 1 ) : NEW_LINE INDENT lis [ i ] = lis [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( result < lis [ i ] ) : NEW_LINE INDENT result = lis [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT def minimumNumberOfDeletions ( arr , n ) : NEW_LINE INDENT len = lis ( arr , n ) NEW_LINE return ( n - len ) NEW_LINE DEDENT arr = [ 30 , 40 , 2 , 5 , 1 , 7 , 45 , 50 , 8 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Minimum ▁ number ▁ of ▁ deletions ▁ = ▁ " , minimumNumberOfDeletions ( arr , n ) ) NEW_LINE