Longest Increasing Subsequence using Longest Common Subsequence Algorithm | Function to return the size of the longest increasing subsequence ; Create an 2D array of integer for tabulation ; Take the second sequence as the sorted sequence of the given sequence ; Classical Dynamic Programming algorithm for Longest Common Subsequence ; Return the ans ; Driver code
def LISusingLCS ( seq ) : NEW_LINE INDENT n = len ( seq ) NEW_LINE L = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE sortedseq = sorted ( seq ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT L [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( seq [ i - 1 ] == sortedseq [ j - 1 ] ) : NEW_LINE INDENT L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ n ] [ n ] NEW_LINE DEDENT sequence = [ 12 , 34 , 1 , 5 , 40 , 80 ] NEW_LINE print ( LISusingLCS ( sequence ) ) NEW_LINE