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