Longest increasing subsequence How can I find the longest increasing subsequence of numbers in the sequence {3,2,6,4,5,1}?
Same question for ABCBDAB
Why would being able to solve these types of problems be important in Relational Algebra?
Thank you in advance for you assistance. 
This question is continued on here
 A: I don’t know what its specific connection with relational algebra is, but the longest increasing subsequence problem appears to have connections with quite a few areas of mathematics. Your two problems are small enough to be solved by inspection. If you want to be more systematic, you could simply enumerate the maximal increasing subsequences of length greater than $1$ (where maximal simply means that this particular subsequence cannot be extended any further):
$$\begin{align*}
&3,6\\
&3,4,5\\
&2,6\\
&2,4,5\\
&4,5
\end{align*}$$
Evidently there are two longest increasing subsequences of $\langle 3,2,6,4,5,1\rangle$: $\langle 3,4,5\rangle$, and $\langle 2,4,5\rangle$.
The same technique will quickly find the unique longest increasing subsequence of the string $ABCBDAB$.
A: This is a classical exercise in dynamic programming, which solves the problem in $n^2$ time (i.e. doubling the sequence length increases the solution time by 4). Suppose we have an array $(s_1,\ldots,s_n)$.


*

*Allocate an array $a$ of size $n$. Element $a_i$ will hold the length of the longest increasing sub-sequence that ends with $s_i$.

*Set $s_1 = 1$, and for $2 \le i \le n$, calculate $a_i$. This just involves taking the maximum value of $a_j+1$ for all $j < i$ such that $s_j \le s_i$.

*Find the largest $a_r$ in the array.


This gives you the length of the longest increasing sub-sequence. And you can find the sequence itself by constructing it backwards from the largest $a_r$: at each value $s_i$ with $a_i \ge 2$, you know that there must be an earlier $s_j$ for which $a_j = a_i - 1$.
