1
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ What exactly is a subsequence for you ? $\endgroup$ – nicomezi Feb 28 '16 at 1:53
  • $\begingroup$ @nicomezi please see my edit $\endgroup$ – MortalMan Feb 28 '16 at 1:55
  • $\begingroup$ Nice problem. It looks like you can use dynamic programming. What is this project for? Is it for a dynamic programming class? $\endgroup$ – Michael Feb 28 '16 at 2:41
  • $\begingroup$ 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$. $\endgroup$ – Michael Feb 28 '16 at 3:19
  • $\begingroup$ @Michael Could you please provide an answer? I am confused. $\endgroup$ – MortalMan Feb 28 '16 at 17:18
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.