Longest Common Increasing Subsequence ( LCS + LIS ) | Returns the length and the LCIS of two arrays arr1 [ 0. . n - 1 ] and arr2 [ 0. . m - 1 ] ; table [ j ] is going to store length of LCIS ending with arr2 [ j ] . We initialize it as 0 , ; Traverse all elements of arr1 [ ] ; Initialize current length of LCIS ; For each element of arr1 [ ] , traverse all elements of arr2 [ ] . ; If both the array have same elements . Note that we don 't break the loop here. ; Now seek for previous smaller common element for current element of arr1 ; The maximum value in table [ ] is out result ; Driver Code
def LCIS ( arr1 , n , arr2 , m ) : NEW_LINE INDENT table = [ 0 ] * m NEW_LINE for j in range ( m ) : NEW_LINE INDENT table [ j ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT current = 0 NEW_LINE for j in range ( m ) : NEW_LINE INDENT if ( arr1 [ i ] == arr2 [ j ] ) : NEW_LINE INDENT if ( current + 1 > table [ j ] ) : NEW_LINE INDENT table [ j ] = current + 1 NEW_LINE DEDENT DEDENT if ( arr1 [ i ] > arr2 [ j ] ) : NEW_LINE INDENT if ( table [ j ] > current ) : NEW_LINE INDENT current = table [ j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT result = 0 NEW_LINE for i in range ( m ) : NEW_LINE INDENT if ( table [ i ] > result ) : NEW_LINE INDENT result = table [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr1 = [ 3 , 4 , 9 , 1 ] NEW_LINE arr2 = [ 5 , 3 , 8 , 9 , 10 , 2 , 1 ] NEW_LINE n = len ( arr1 ) NEW_LINE m = len ( arr2 ) NEW_LINE print ( " Length ▁ of ▁ LCIS ▁ is " , LCIS ( arr1 , n , arr2 , m ) ) NEW_LINE DEDENT