Longest Increasing Subsequence | DP | lis returns length of the longest increasing subsequence in arr of size n ; Declare the list ( array ) for LIS and initialize LIS values for all indexes ; Compute optimized LIS values in bottom up manner ; Initialize maximum to 0 to get the maximum of all LIS ; Pick maximum of all LIS values ; Driver program to test above function
def lis ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE lis = [ 1 ] * n NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( 0 , 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 maximum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT maximum = max ( maximum , lis [ i ] ) NEW_LINE DEDENT return maximum NEW_LINE DEDENT arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] NEW_LINE print " Length ▁ of ▁ lis ▁ is " , lis ( arr ) NEW_LINE