CLR cover

Problem 121: Longest Increasing Subsequence

In this problem we consider a word $x$ on the alphabet of positive integers. An increasing subsequence of $x$ is a subsequence $x[i_0]x[i_1]\cdots x[i_{\ell-1}]$, where $0\leq i_0\lt i_1\lt \cdots \lt i_{\ell-1}\lt |x|$ and $x[i_0]\leq x[i_1]\leq \cdots \leq x[i_{\ell-1}]$.

Show that Algorithm Lis computes in place the maximal length of an increasing subsequence of a word $x$ in time $O(|x| \log |x|)$.

Lis$(x \textrm{ non-empty word over positive integers})$ 
    \begin{algorithmic}
 \STATE $\ell\leftarrow 1$
 \FOR{$i\leftarrow 1$ \TO $|x|-1$}
  \STATE $(a,x[i])\leftarrow (x[i],\infty)$
  \STATE $k\leftarrow \min\{j \mid 0\leq j\leq \ell \mbox{ and } a\lt x|j]\}$
  \STATE $x[k]\leftarrow a$
  \IF{$k = \ell$}
   \STATE $\ell\leftarrow \ell+1$
  \ENDIF
 \ENDFOR
\RETURN{$\ell$}
    \end{algorithmic}

Inspecting carefully Algorithm Lis, it should be noticed that the word $x[0\dd \ell-1]$ computed when the algorithm terminates is increasing but not usually a subsequence of $x$, as shown by the example, which leads to the next question.

Design an algorithm that computes a longest increasing subsequence of a word $x$ in time $O(|x| \log |x|)$.

References

  • M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence and application. Inf. Comput., 208(9):1054-1059, 2010.
  • M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.
  • S. S. Skiena. The Algorithm Design Manual. Springer, 2008. 2nd edition.
  • I.-H. Yang, C.-P. Huang, and K.-M. Chao. A fast algorithm for computing a longest increasing subsequence. Inf. Process. Lett., 93(5):249-253, 2005.