2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ I can't answer your second question, but for the sequences you provided you can find the longest increasing subsequence(s) simply by inspection. Given a sequence $\{a_n\}_{n\ge 1}$, if you graph the points $(n,a_n)$ it lends a nice visualization to the problem. $\endgroup$
    – Doc
    Nov 19 '13 at 16:48
  • $\begingroup$ Hello @Doc, you were right, putting the points on a graph did help a lot. I have a similar question with many more points in an array and using an Excel scatter plot helps to find the longest subsequence. $\endgroup$ Nov 20 '13 at 9:42
  • $\begingroup$ Splendid. Glad it helped. $\endgroup$
    – Doc
    Nov 20 '13 at 13:39
  • $\begingroup$ Hi Craig, I responded to you at the continuation post here: math.stackexchange.com/questions/574487/… $\endgroup$
    – Steve Kass
    Nov 25 '13 at 14:03
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Hello, Thank you for you answer. The subject comes from Itzik Ben-Gan's TSQL-Querying. The section on LISLP comes right after calculating algorithim complexities. Still not sure why its included. $\endgroup$ Nov 20 '13 at 8:51
  • $\begingroup$ @Craig: You’re welcome. A brief Google search seems to indicate that there is a connection with SQL, but I didn’t investigate further. $\endgroup$ Nov 20 '13 at 18:52
  • $\begingroup$ Hello, thanks for checking that out. I asked the same question again for another series of sequences but this time much longer and in an array. $\endgroup$ Nov 21 '13 at 8:23
  • $\begingroup$ This is exponential, isn't it? That makes it unusable for sequences with more than than about 20 elements. But there is a perfectly simple $n^2$ algorithm available $-$ see my answer for details. $\endgroup$
    – TonyK
    Nov 25 '13 at 9:40
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Hello and thank you for your reply. I updated my question with a link to the second part of the original question. If a is the array, what goes in j and in i? Could you provide an answer using the data I provided in my second question. $\endgroup$ Nov 25 '13 at 9:44
  • $\begingroup$ For the above question: using set {3,2,6,4,5,1}, what would be i & j $\endgroup$ Nov 25 '13 at 11:27
  • $\begingroup$ $a = (1,1,2,2,3,1)$. $\endgroup$
    – TonyK
    Nov 25 '13 at 12:10

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.