Problem: “Find LCS of <N,I,A,C,U,E> and <N,I,C,E,A,C>.”
Solution: Set up a table (2D array):
j \ i | 0 | N | I | A | C | U | E |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
N | 0 | ||||||
I | 0 | ||||||
C | 0 | ||||||
E | 0 | ||||||
A | 0 | ||||||
C | 0 |
Then, for every cell:
The LCS length is the lowest rightmost cell. To find which elements are included in the subsequence, follow the arrows and record every cell that has a diagonal arrow pointing from it (it will be in reverse):
LCS = 4 — [N, I, A, C]
Worst-case complexity: O(m × n)
Extending:
To turn this into longest common increasing subsequence, create an array of elements from minimum to maximum, and then find LCS between this array and the input.