Formal Definition

A sequence is a list $X = \langle x_1, x_2, \ldots, x_m\rangle$ (e.g., $\langle A,B,C,B,D,A,B \rangle$).

A subsequence of X is an ordered sublist of X (e.g., $\langle B,C,D,B \rangle$, but not $\langle D,C,B \rangle$).

A common subsequence of two sequences X and $Y=\langle B,D,C,A,B\rangle$ is a subsequence of both of them.

The LCS, or longest common subsequence of X and Y is, well, their longest possible common subsequence. What is it?

We'll also use X_i to mean the i-element prefix of X. So X_m = X if X is length m.