CompProg, Kapitel 2.3

2.3 Longest increasing subsequence

Again we are given an array of integers. We want to compute the (or rather: a) longest increasing subsequence. A subsequence of a sequence $\vec{a} = [a_{1}, a_{2}, \dots, a_{n}]$ is a sequence of the form $\vec{b} = [a_{j_{1}}, a_{j_{2}}, \dots, a_{j_{k}}]$ with $1 \leq j_{1} < j_{2} < \dots < j_{k} \leq n$ . More intuitively: a sequence that can be formed by deleting entries in $\vec{a}$ . The subsequence $\vec{b}$ is increasing if

\begin{array}{r} a_{j_{1}} < a_{j_{2}} < a_{j_{3}} < \dots < a_{j_{k}} . \end{array}

We write ISS for increasing subsequence and LISS for longest increasing subsequence. Here is an example:

So $[8, 9, 11, 12]$ is an ISS (increasing subsequence), albeit not a longest one. That would be this one:

Longest increasing subsequence differs from the previous two problems in that even the most trivial (and inefficient) algorithm is not completely trivial.

Exercise 2.3.1 Write test cases as described in Chapter 2.1

An exponential algorithm

Here is a simple recursive idea: let $A = [a_{0}, \dots, a_{n - 1}]$ be the input array. We set $B = [a_{0}, \dots, a_{n - 2}]$ and $x = a_{n - 1}$ . There are two cases: (1) there is a LISS of $A$ that does not contain the last element $x$ ; in this case $LISS (A) = LISS (B)$ . (2) every LISS of $A$ contains the last index; then it must be of the form $S + [x]$ with $S$ being a LISS of $B$ . But this means that all elements of $S$ (in particular the last one) are strictly less than $x$ . This suggests the following algorithm:

Compute $LISS (B)$ .
Compute the longest increasing subsequence $S$ of $B$ whose maximum entry is less than $x$ ; then append $x$ .
Take the better of the two.

Note that in Point 2, we have to answer a more general question: what is the longest increasing subsequence with a specified upper bound.

Problem 2.3.2 Implement the above idea. Specifically, implement a recursive function longest_increasing_subsequence_less_than(array, upper_bound). You can then find the overall longest increasing subsequence by calling it with upper_bound being $+ \infty$ .

A quadratic algorithm

The previous idea was inefficient because a call to longest_increasing_subsequence_less_than(array, inf) might entail an exponential number of recursive calls. But how many different input arguments (array, upper_bound) will the function encounter? There are at most $n + 1$ possibilities for array, since each will be a prefix of the original input array, i.e., will be of the form input_array[0:j]. The variabel upper_bound is $+ \infty$ at the beginning, but afterwards only values occurring in the input value will be passed as upper_bound; thus, at most $n + 1$ values will ever occur, and the total number of combinations (array, upper_bound) is at most $(n + 1)^{2}$ . We could just store function calls in a dictionary and will end up with a (somewhat) quadratic algorithm. However, the right way to do things in such a case is to use dynamic programming to search the possibilities systematically.

To actually implement it, we turn things on their head, in a way. Rather than computing, for each index $j$ and upper bound $θ$ the longest increasing subsequence of $A [0 : j]$ all whose elements are $< θ$ , we do the following: for each index $j$ and desired length $k$ , compute, among all increasing subsequences $\vec{b}$ in $A [0 : j]$ that have length $k$ , the one whose maximum entry $max (\vec{b})$ is smallest. That is,

\begin{array}{r} T_{k}^{(j)} := min {max (\vec{b}) | \vec{b} is ISS of A [0 : j], \vec{b} has length k} . \end{array}

Note that if $A [0 : j]$ does have any ISS of length $k$ , then we take a minimum over the empty set and thus $T_{k}^{(j)}$ would be empty. On the other hand, for $j = 0$ the array $A [0 : 0]$ is the empty array, which has only one increasing subsequence: the empty sequence itself; the maximum of the empty sequence is the maximum over an empty set, thus it is $- \infty$ , and therefore $T_{0}^{(0)} = 0$ . Another insight: it holds that $T_{0}^{(j)} \leq T_{1}^{(j)} \leq T_{2}^{(j)} \leq \dots$ . This is because an ISS of length $k + 1$ contains an ISS of length $k$ , so the definition of $T {(j)}_{k}$ takes a minimum over a potentially larger set than $T {(j)}_{k + 1}$ , giving a smaller or equal value.

How to compute the values of $T_{*}^{(j + 1)}$ when given $T_{*}^{(j)}$ ? Let $x := A [j]$ . Let $k$ be such that

\begin{array}{r} (1) & T_{k - 1}^{(j)} < x \leq T_{k}^{(j)} . \end{array}

Since $T_{0}^{(j)} = - \infty$ and $T_{n}^{(j)} = + \infty$ for all $j \leq n - 1$ , and the $T_{l}^{(j)}$ are increasing in $l$ , there is one unique such $k$ . To build an ISS of length $k$ in $A [0 : j]$ , we can take an ISS of $A [0 : j]$ of length $k - 1$ ending in $T_{k - 1}^{(j)}$ , append $x$ , and obtain an ISS of $A [0 : j + 1]$ of length $k$ ending in $x$ . Or we could just take an ISS of length $k$ in $A [0 : j]$ . Either way, it holds that

\begin{array}{r} T_{k}^{(j + 1)} = min (x, T_{k}^{(j)}) . \end{array}

What about $l > k$ ? Since $T_{l}^{(j)} \geq T_{k}^{(j)} \geq x$ , $x$ cannot be appended to any ISS in $A [0 : j]$ of length $l$ ; it would not be an increasing sequence anymore. Therefore:

\begin{array}{r} T_{l}^{(j + 1)} = T_{l}^{(j)} for all l \geq k + 1 . \end{array}

What about $l \leq k - 1$ ? Take an ISS of length $l - 1$ in $A [0 : j]$ . Maybe we can append $x$ to form an ISS of length $l$ ending in $x$ ; but we already have one ending in $T_{l}^{(j)} \leq T_{k - 1}^{(j)} < x$ , so appending $x$ would just give a worse (i.e., higher-ending) ISS than we already have. The row $j + 1$ thus differs from row $j$ in at most one position. To summarize:

\begin{aligned} T_{k}^{(j + 1)} & = min (x, T_{k}^{(j)}) for k such that T_{k - 1}^{(j)} < x \leq T_{k}^{(j)}, \\ T_{l}^{(j + 1)} & = T_{l}^{(j)} for all l \neq k . \end{aligned}

In the example run below, we don't keep row for every $j$ . We just show the values $T_{k}^{(j)}$ for the current $j$ and cross out numbers that have been replaced by better ones.

Once we have processed all elements, we have arrived at $T_{k}^{(n)}$ , which is the smallest possible value a ISS of size $k$ can end with. The largest $k$ for which this is not $+ \infty$ is the length of a LISS.

Problem 2.3.3 Implement the idea that we just outlined. Start with a program that computes the length of the longest increasing subsequence, not the sequence itself.

Computing the sequence itself

We want our program to output a longest sequence, not just its length. To facilitate judging the correctness, the answer should be unique, so we have to come up with tie breaking rules: when two increasing subsequences $b_{1} < b_{2} < \dots < b_{k}$ and $c_{1} < c_{2} < \dots < c_{k}$ have the same size, we prefer one with the smallest values. But what does that even mean? Couldn't it be that one LISS is $[4, 5, 21]$ and the other is $[7, 8, 19]$ ? In that case, which one has "smaller values"? It turns out that there is always a unique minimum that is minimal in every position:

Theorem 2.3.1 Suppose $[b_{1}, \dots, b_{k}]$ and $[c_{1}, \dots, c_{k}]$ are both LISS of the array $A$ . Then

\begin{array}{r} min (b_{1}, c_{1}), min (b_{2}, c_{2}), \dots, min (b_{k}, c_{k}) \end{array}

is also a LISS of $A$ .

Remark: It is pretty easy to show that the new sequence is increasing. In fact, this holds even if $\vec{b}$ and $\vec{a}$ are not necessarily longest ISS of $A$ . However, it might be that the new sequence is not a subsequence of $A$ ! For example, when $A = [2, 3, 1, 4]$ and $\vec{a} = [2, 3]$ and $\vec{b} = [1, 4]$ then the pointwise minimum would be $[1, 3]$ , but now this is not a subsequence of $A$ anymore. To prove that this cannot occur, you must use that $\vec{a}$ and $\vec{b}$ are, in fact, longest increasing subsequences of $A$ .

Problem 2.3.4 Add bookkeeping to your implementation such that it does not only output the length of the LISS but the LISS with minimal values itself.

python quadratic.py < testcases/example-from-lecture-notes.in                             
6
4 6 7 8 11 12

Problem 2.3.5 Improve your implementation of the quadratic algorithm: in order to find the $k$ for which ( $1$ ) holds, don't use linear search; use binary search.