the lcs algorithm the definition of , satisfies subproblem optimizationfor we cannot have longest common subsequence without also having longest common subsequences for the subproblems alsoit uses subproblem overlapbecause subproblem solution , can be used in several other problems (namelythe problems + , , + and + , + turning this definition of , into an algorithm is actually quite straightforward we create an ( ( arrayldefined for < < and < < we initialize all entries to in particular so that all entries of the form , and , are zero thenwe iteratively build up values in until we have ln, the length of longest common subsequence of and we give python implementation of this algorithm in code fragment def lcs(xy) """return table such that [ ][kis length of lcs for [ :jand [ : "" nm len( )len(yintroduce convenient notations ( + ( + table [[ ( + for in range( + ) for in range( ) for in range( ) if [ = [ ]align this match [ + ][ + [ ][ elsechoose to ignore one character [ + ][ + max( [ ][ + ] [ + ][ ] return code fragment dynamic programming algorithm for the lcs problem the running time of the algorithm of the lcs algorithm is easy to analyzefor it is dominated by two nested for loopswith the outer one iterating times and the inner one iterating times since the if-statement and assignment inside the loop each requires ( primitive operationsthis algorithm runs in (nmtime thusthe dynamic programming technique can be applied to the longest common subsequence problem to improve significantly over the exponential-time brute-force solution to the lcs problem the lcs function of code fragment computes the length of the longest common subsequence (stored as ln, )but not the subsequence itself fortunatelyit is easy to extract the actual longest common subsequence if given the complete table of , values computed by the lcs function the solution can be reconstructed back to front by reverse engineering the calculation of length ln, at any position , if yk then the length is based on the common subsequence associated with length - , - followed by common character we can record as part of the sequenceand then continue the analysis from - , - if yk