# Clear solution for longest increasing subsequence

I have to code an algorithm for finding the longest increasing subsequence of an integer list. I know there are tons of code solutions for this, but I am looking for a clear explanation of how to find it.

Say the list is 9 44 32 12 7 42 34 92, an increasing subsequence would be 9 32 42 92

I can't find an algorithm in words on how to find the solution - that is what I am looking for here.

Thanks!

• What exactly is a subsequence for you ? – nicomezi Feb 28 '16 at 1:53
• @nicomezi please see my edit – MortalMan Feb 28 '16 at 1:55
• Nice problem. It looks like you can use dynamic programming. What is this project for? Is it for a dynamic programming class? – Michael Feb 28 '16 at 2:41
• If your list has $n$ integers and is $\{x_1, ..., x_n\}$, a hint is to define $J_k(x)$ as the longest remaining portion of your increasing subsequence, which selects from $\{x_k, ..., x_n\}$, given that all selections on this remaining portion are larger than $x$. You can compute $J_n(x)$ easily (it is 1 if $x_n>x$, and 0 else). Then compute backwards: Knowing $J_{k+1}(x)$ for all relevant $x$, compute $J_k(x)$ for all relevant $x$. – Michael Feb 28 '16 at 3:19
• @Michael Could you please provide an answer? I am confused. – MortalMan Feb 28 '16 at 17:18

## 1 Answer

This is answer is based on the comment by Michael.

Assume that the sequence be given by integers $x_1, \ldots, x_n$. Let $J_k(x)$ denote the longest increasing subsequence of the list consisting of elemnts $x_k, x_{k+1}, \ldots, x_n$ if all chosen elements must be greater or equal to $x$.

In your example sequence you would get $J_5(35) = 2$ since the longest subsequence of 7 42 34 92 consisting of numbers which are at least 35 is the list 42 92.

All quantities $J_k(x)$ can be computed using dynamic programming. You begin with values $J_n(x)$ for all $x$. These values can be computed by noting that $J_n(x) = 1$ if and only if $x \leq x_n$.

Assume that $J_k(x)$ has been computed for all $x$. Then $J_{k-1}(x)$ can be computed as follows: If $x_{k-1} < x$ then $x_{k-1}$ must not be chosen and it holds that $J_{k-1}(x) = J_k(x)$. Otherwise, $x_{k-1}$ might be chosen. If it is chosen, then $J_{k-1}(x) = J_k(x_{k-1}) + 1$ since the remaining subsequence must only use items of value at least $x_{k-1}$ to keep the list increasing. If it is not chosen, then $J_{k-1}(x) = J_k(x)$ as before. To sum up, $$J_{k-1}(x) = \begin{cases} J_k(x), & \text{if } x > x_{k-1} \text{ or } J_k(x) \geq J_k(x_{k-1}) + 1 \\ J_k(x_{k-1}) + 1, & \text{else.} \end{cases}$$