Uncrossed Lines
Two rows of numbers are written out. You may draw a line joining a number in the first row to an EQUAL number in the second row. Each number may be used by at most one line, and no two lines may CROSS.
Print the most lines that can be drawn.
1 4 2 / 1 2 4 -> 2
2 5 1 2 5 / 10 5 2 1 5 2 -> 3
In the first example, joining the two 1s and then the two 4s would cross the line
joining the 2s, so only two lines fit.
## What "no crossing" means
Lines (i1, j1) and (i2, j2) cross exactly when i1 < i2 and j1 > j2, or the
mirror. So a legal set of lines, sorted by its first endpoints, has its second endpoints
increasing too.
That is the definition of a COMMON SUBSEQUENCE: an increasing sequence of positions in each row, matched in order, with equal values at matched positions.
So the answer is the longest common subsequence of the two rows, and the whole problem is recognising that. Problem #237 does the work.
## The recognition is the content
Nothing about the statement mentions subsequences. It talks about lines and crossings, and the reduction is a geometric observation: "no crossing" and "matched in increasing order" are the same condition written two ways.
Problems like this are common in interviews precisely because the reduction is the test. The recurrence, once found, is four lines that most candidates already know.
## The recurrence, over integers rather than characters
``` dp[i][j] = the longest common subsequence of the first i and first j numbers
a[i-1] == b[j-1] -> dp[i][j] = dp[i-1][j-1] + 1 otherwise -> dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) ```
Identical to the string version. The elements happen to be numbers, which changes nothing: the algorithm only ever tests equality.
That is worth noticing in the other direction too. A solution written for characters works unchanged for numbers, for pairs, for anything comparable, and specialising it to a 26-letter alphabet would have thrown that away for nothing.
## Boundaries
[1] / [1] answers 1 and [1] / [2] answers 0.
[1,1,1] / [1,1] answers 2: the shorter row limits the count, and repeated values must
each be matched separately rather than as a group.
[3,2,1] / [1,2,3] answers 1. Every value is shared and the orders are reversed, so any
two lines would cross.
[1,2,3] / [4,5,6] answers 0, with nothing in common.
## Cost
Time O(n m). Space O(m) with two rows.