A really 'cute' problem popped up in our Data Structures & Algorithms homework and I wanted to write about it.

If you're in the class this will obviously ruin the fun, so read it later, after you're done!

The goal is to find the longest common increasing subsequence. Some notes:

- A
**subsequence**of $$ s $$ is a set $$ v $$ such that $$ v \subset s $$, and the items in $$ v $$ appear in the same order as they appear in $$ s $$. - An
**increasing subsequence**of $$ s $$ is a subsequence $$ v $$ such that:

$$ v_1 < v_2 < ... < v_n $$

The problem calls for some $$ s $$ and some \( t \), returning the longest subsequence common between the sets. It is described roughly in this link and a sample solution is described in a following blog post.

Defining $$ LCIS(s_{1}...s_{n},t_{1}...t_{m},last) $$ recursively:

- If $$ s_{n} = t_{m} $$ and $$ s_{n} > last $$, then

$$ LCIS = max( LCIS(s_{1}...s_{n-1},t_{1}...t_{m-1},s_{n})+1, LCIS(s_{1}...s_{n-1},t_{1}...t_{m},last), LCIS(s_{1}...s_{n},t_{1}...t_{m-1},last) ) $$

- If \( s_{n}\neq t_{m} \), then

$$ LCIS=max( LCIS(s_{1}...s_{n-1},t_{1}...t_{m},last), LCIS(s_{1}...s_{n},t_{1}...t_{m-1},last) ) $$

Which is fine and dandy, but it's a super slow recurrence. Think about how many times $$ LCIS(s_1...s_2, t_1...t_2) $$ will be invoked.

Instead, we'll use *Dynamic Programming*, which is much less exciting then it sounds. (I don't know about you, but I expect some serious magic, like lasers, from that kind of name.)

The basic idea of dynamic programming is to define an **optimal substructure** and discover **overlapping subproblems**. Then, we compute the value of the overlapping subproblems in a **bottom up fashion**, usually via a table or a set of vectors.

The recurrence we defined above is an **optimal substructure** since it will allow us to utilize overlapping calls. (Like $$ LCIS(s_1...s_2, t_1...t_2) $$)

Examining the problem closely, It's possible to solve this problem using two arrays instead of a matrix. We'll use $$ c $$ which stores the length of the LCIS ending at a given element $$ i $$ and $$ p $$ which stores the previous element of the LCIS (used for reconstruction).

The Rust code below is well commented and includes a number of tests.

```
use max;
use RingBuf;
/// Longest Common Increasing Sequence
///
/// Accepts two `Vec<int>`s and returning a `Vec<int>` Which is the LCIS.
///
/// Note: There are multiple Longest Common Increasing Sequences in most inputs.
/// For example, `[5, 3, 6, 2, 7, 1, 8]` and `[1i, 2, 3, 4, 5, 6, 7, 8, 9]` have
/// multiple valid results: `[5i, 6, 7, 8]`, `[3i, 6, 7, 8]`, ...
///
/// Single result LCIS Test Suite
///
/// These tests we know the (only) answer to, so we can test for the answer.
/// Multiple Results Test Suite
///
/// These results we know only the length of, but we can test the validity the
/// sequence.
```