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!
 A: 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}
$$
