Construction of Longest Increasing Subsequence ( LIS ) and printing LIS sequence | Utility function to print LIS ; Function to construct and print Longest Increasing Subsequence ; L [ i ] - The longest increasing sub - sequence ends with arr [ i ] ; L [ 0 ] is equal to arr [ 0 ] ; start from index 1 ; do for every j less than i ; L [ i ] = { Max ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] < arr [ i ] ; L [ i ] ends with arr [ i ] ; L [ i ] now stores increasing sub - sequence of arr [ 0. . i ] that ends with arr [ i ] ; LIS will be max of all increasing sub - sequences of arr ; max will contain LIS ; Driver Code ; construct and print LIS of arr
def printLIS ( arr : list ) : NEW_LINE INDENT for x in arr : NEW_LINE INDENT print ( x , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def constructPrintLIS ( arr : list , n : int ) : NEW_LINE INDENT l = [ [ ] for i in range ( n ) ] NEW_LINE l [ 0 ] . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if arr [ i ] > arr [ j ] and ( len ( l [ i ] ) < len ( l [ j ] ) + 1 ) : NEW_LINE INDENT l [ i ] = l [ j ] . copy ( ) NEW_LINE DEDENT DEDENT l [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT maxx = l [ 0 ] NEW_LINE for x in l : NEW_LINE INDENT if len ( x ) > len ( maxx ) : NEW_LINE INDENT maxx = x NEW_LINE DEDENT DEDENT printLIS ( maxx ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 2 , 6 , 4 , 5 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE constructPrintLIS ( arr , n ) NEW_LINE DEDENT