Longest Increasing Subsequence | DP | To make use of recursive calls , this function must return two things : 1 ) Length of LIS ending with element arr [ n - 1 ] . We use max_ending_here for this purpose 2 ) Overall maximum as the LIS may end with an element before arr [ n - 1 ] max_ref is used this purpose . The value of LIS of full array of size n is stored in * max_ref which is our final result ; Base Case ; maxEndingHere is the length of LIS ending with arr [ n - 1 ] ; Recursively get all LIS ending with arr [ 0 ] , arr [ 1 ] . . arr [ n - 2 ] IF arr [ n - 1 ] is maller than arr [ n - 1 ] , and max ending with arr [ n - 1 ] needs to be updated , then update it ; Compare maxEndingHere with overall maximum . And update the overall maximum if needed ; Return length of LIS ending with arr [ n - 1 ] ; The wrapper function for _lis ( ) ; maximum variable holds the result ; The function _lis ( ) stores its result in maximum ; returns max ; Driver program to test the above function
global maximum NEW_LINE def _lis ( arr , n ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return 1 NEW_LINE DEDENT maxEndingHere = 1 NEW_LINE for i in xrange ( 1 , n ) : NEW_LINE INDENT res = _lis ( arr , i ) NEW_LINE if arr [ i - 1 ] < arr [ n - 1 ] and res + 1 > maxEndingHere : NEW_LINE INDENT maxEndingHere = res + 1 NEW_LINE DEDENT DEDENT maximum = max ( maximum , maxEndingHere ) NEW_LINE return maxEndingHere NEW_LINE DEDENT def lis ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE maximum = 1 NEW_LINE _lis ( arr , n ) NEW_LINE return maximum NEW_LINE DEDENT arr = [ 10 , 22 , 9 , 33 , 21 , 50 , 41 , 60 ] NEW_LINE n = len ( arr ) NEW_LINE print " Length ▁ of ▁ lis ▁ is ▁ " , lis ( arr ) NEW_LINE