LCS & LIS — DP Table Fill, Traceback, and Patience Piles

LCS: fill the O(nm) table (match → diagonal +1, mismatch → max of up/left), then trace back to read the actual subsequence. LIS: deal values into patience piles; the pile count is the LIS length.

step 0

LCS DP table   dp[i][j] = LCS(X[0..i), Y[0..j))

Match → dp[i-1][j-1] + 1 (diagonal). Mismatch → max(dp[i-1][j], dp[i][j-1]).
row i (X char) col j (Y char) source neighbor current cell traceback path
Press Step to begin filling the table cell by cell.
step 0

Input array (current element highlighted)

Patience piles   (place x on leftmost pile whose top ≥ x; pile count = LIS length)

tails[p] = smallest tail of any increasing subsequence of length p+1. len(tails) is the running LIS length.
Press Step to deal the first value onto a pile.
Self-contained visualization. LCS uses the counting recurrence; LIS uses the patience / binary-search method. The tails array tracks lengths, not a valid subsequence — see middle.md for parent-pointer reconstruction and professional.md for the proof that tails stays sorted.