The algorithms to find the longest increasing subsequence in a sequence are discussed in various places (including Wikipedia), but in my opinion their exposition is not intuitive.
M[j] — stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i.
Precise and succinct but not easy to parse and grasp.
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. It is a set of characters that appear in left-to-right order, but not necessarily consecutively.
Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.
Problem definition of Longest Common Subsequence
- Given the first sequence which contains (m) symbols X = (x1, x2, x3, …, xm)
- Given the second sequence which contains (n) symbols Y = (y1,