Longest Monotonically Increasing Subsequence

 Today, let’s take a look at another interesting exercise given in the CLRS book [1].

Problem Statement

Exercise 15.4-6

Give an $O(n \cdot log_2 n)-$ time algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers. (Hint: Observe that the last element of a candidate subsequence of length $i$ is at least as large as the last element of a candidate subsequence of length $i - 1$. Maintain candidate subsequences by linking them through the input sequence.)

Longest Monotonically Increasing Subsequence - Approach

There may be many different approaches to solve this problem. However, we are going to describe one such approach that we came up with. Each approach has its own strengths and weaknesses. The book [1] suggests a different approach to what we are going to present here. Nonetheless, both the approaches have the same asymptotic time and space complexity.

Our approach uses an auxiliary array $m$ to store intermediate results. Finally, this array should contain the longest monotonically increasing subsequence of the given input sequence. Our loop invariant is such that this auxiliary array $m$ is always sorted. Before the first iteration of the loop, this auxiliary array $m$ is empty and so it is trivially sorted. At each iteration of the for-loop, we get the next element of the input sequence $a[i]$, and find the index $s$ of the smallest element  in the subsequence $m$ which is greater than or equal to the value $a[i]$, thus $a[i] \le m[s]$. Note that the value of $s$ ranges from $1 \le s \le l + 1$ where $l$ is the current length of the monotonically increasing subsequence. Also note that all the values of $1 \le s \le l$ are legal and $s = l + 1$ is not a legal value. In fact, $s = l + 1$ signifies that the current $a[i]$ value is larger than all the values currently held in $m$, thus we can add it to the end of the monotone increasing subsequence. This leaves the array sorted. Otherwise, we have found a valid successor $s$ which is $a[i] \le m[s]$, so we can merely replace $m[s]$ with a much smaller value of $a[i]$, giving us more wiggle room to insert as many values as we go on. Note that since $m[s]$ is the smallest value which is $a[i] \le m[s]$, it implies that any value to the left of $m[s]$ is less than $a[i]$. Moreover, by transitivity $a[i] \le m[s] \lt m[s + 1]$ implies that $a[i] \lt m[s + 1]$. That implies, replacing $m[s]$ with $a[i]$ leaves the subsequence $m$ sorted. Therefore after the completion of the for-loop, this should give us the longest monotonically increasing subsequence of the given input sequence.
Here’s the pseudocode for finding the longest monotonically increasing subsequence of the given input sequence.

**Input:** array $a$ of $n$ numbers  
**Output:** the longest monotonically increasing subsequence of the given input sequence  
$LIS(a)$  
$\phantom{{}++{}}$ $n \gets a.length$   
$\phantom{{}++{}}$ let $m[1\ldots n]$ be a new array  
$\phantom{{}++{}}$ $l \gets 0$  
$\phantom{{}++{}}$ `for` $i = 1$ to $n$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets SUCCESSOR(m, a[i] - 1, 1, l)$   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $s \le l$    
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $m[s] \gets a[i]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  $l \gets l + 1$   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$  $m[l] \gets a[i]$  
$\phantom{{}++{}}$ `return` $m[1 \ldots l]$ 
   
**Input:** array $a$ of $n$ numbers sorted in monotone increasing order and target value $t$, start position $i$ inclusive and end position $j$ inclusive.   
**Output:** The position of the successor of $t$ in the array if it exists, $n + 1$, otherwise.   
$SUCCESSOR(a, t, i, j)$  
$\phantom{{}++{}}$ $l \gets i$   
$\phantom{{}++{}}$ $r \gets j + 1$    
$\phantom{{}++{}}$ `while` $l \lt r$    
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $m \gets \lfloor (l + r) / 2 \rfloor$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $t \lt a[m]$   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $r \gets m$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $l \gets m + 1$  
$\phantom{{}++{}}$ `return` $r$

Note that our input sequence may contain duplicate values. If we have such values, finding the successor and replacing it with that value gives us duplicate values in our monotone increasing subsequence, which leads to flawed results. Therefore, if the value of $a[i]$ already exists in the monotonically increasing subsequence $m$, we then merely replace it by itself. This doesn’t change the sequence $m$, rather leaving it intact. We use the general procedure SUCCESSOR for our purpose, but we decrement the target value $a[i]$ by one to get the closed interval i.e. values equal to it. If there are no such values, the procedure will return the smallest value which is $\gt a[i]$.

Sample Implementation

Here’s the sample implementation of the algorithms presented above.

Analysis

Our approach calls the procedure binary $SUCCESSOR$ with the subsequence $m$ which takes $log_2 n$ time for each element of the input sequence. Also note that the length $l$ of the subsequence $m$ at any given point in time is $l \le n$ where $n$ is the length of the input sequence $a$. This implies, the value of $l$ is bounded above by $n$. Thus, in the worst case, our approach takes $O(n \cdot log_2 n)-$ time and $O(n)$ space.

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844