both [ ix and [ jy this definition allows us to rewrite [ ,jin terms of optimal subproblem solutions this definition depends on which of two cases we are in (see figure in this casewe have match between the last character of [ iand the last character of [ jwe claim that this character belongs to longest common subsequence of [ iand [ jto justify this claimlet us suppose it is not true there has to be some longest common subsequence ik jk if ik or jk then we get the same sequence by setting and alternatelyif jk then we can get an even longer common subsequence by adding to the end thusa longest common subsequence of [ iand [ jends with thereforewe set [ , ]= [ - , if in this casewe cannot have common subsequence that includes both and that iswe can have common subsequence end with or one that ends with (or possibly neither)but certainly not both thereforewe set [ijmax{ [ - , ] [ij- ]if in order to make both of these equations make sense in the boundary cases when or we assign [ for - and [- for - , , , - the definition of [ ,jabove satisfies subproblem optimizationfor we cannot have longest common subsequence without also having longest common subsequences for the subproblems alsoit uses subproblem overlapbecause subproblem solution [ijcan be used in several other problems (namelythe problems [ ] [ , ]and [ , ]figure the two cases in the longest common subsequence algorithm(ax (bx note that the algorithm stores only the [ ,jvaluesnot the matches the lcs algorithm