Construction of Longest Increasing Subsequence ( N log N ) | Binary search ; Add boundary case , when array n is zero Depend on smart pointers ; Initialized with - 1 ; it will always point to empty location ; new smallest value ; arr [ i ] wants to extend largest subsequence ; arr [ i ] wants to be a potential condidate of future subsequence It will replace ceil value in tailIndices ; driver code
def GetCeilIndex ( arr , T , l , r , key ) : NEW_LINE INDENT while ( r - l > 1 ) : NEW_LINE INDENT m = l + ( r - l ) // 2 NEW_LINE if ( arr [ T [ m ] ] >= key ) : NEW_LINE INDENT r = m NEW_LINE DEDENT else : NEW_LINE INDENT l = m NEW_LINE DEDENT DEDENT return r NEW_LINE DEDENT def LongestIncreasingSubsequence ( arr , n ) : NEW_LINE INDENT tailIndices = [ 0 for i in range ( n + 1 ) ] NEW_LINE prevIndices = [ - 1 for i in range ( n + 1 ) ] NEW_LINE len = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( arr [ i ] < arr [ tailIndices [ 0 ] ] ) : NEW_LINE INDENT tailIndices [ 0 ] = i NEW_LINE DEDENT elif ( arr [ i ] > arr [ tailIndices [ len - 1 ] ] ) : NEW_LINE INDENT prevIndices [ i ] = tailIndices [ len - 1 ] NEW_LINE tailIndices [ len ] = i NEW_LINE len += 1 NEW_LINE DEDENT else : NEW_LINE INDENT pos = GetCeilIndex ( arr , tailIndices , - 1 , len - 1 , arr [ i ] ) NEW_LINE prevIndices [ i ] = tailIndices [ pos - 1 ] NEW_LINE tailIndices [ pos ] = i NEW_LINE DEDENT DEDENT print ( " LIS ▁ of ▁ given ▁ input " ) NEW_LINE i = tailIndices [ len - 1 ] NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT print ( arr [ i ] , " ▁ " , end = " " ) NEW_LINE i = prevIndices [ i ] NEW_LINE DEDENT print ( ) NEW_LINE return len NEW_LINE DEDENT arr = [ 2 , 5 , 3 , 7 , 11 , 8 , 10 , 13 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " LIS size " , LongestIncreasingSubsequence ( arr , n ) ) NEW_LINE