Longest Increasing Subsequence

Longest increasing subsequence problem

Another problem we considered in the previous chapter was computing the length of the longest increasing subsequence of a given array $A[1 .. n]$ of numbers. We developed two different recursive backtracking algorithms for this problem. Both algorithms run in $O(2^n)$ time in the worst case; both algorithms can be sped up significantly via dynamic programming.

First recurrence: Is this next?

Our first backtracking algorithm evaluated the function $LISbigger(i, j)$, which we defined as the length of the longest increasing subsequence of $A[ j .. n]$ in which every element is larger than $A[i]$. We derived the following recurrence for this function:

$$LISbigger(i,j)= \begin{cases} & \text{ 0 } \hspace{5.9cm} if\space j>n \\ & LISbigger(i,j+1) \hspace{3.3cm} if\space A[i]\geq A[j] \\ & max\begin{Bmatrix} & LISbigger(i,j+1)\\ & 1+LISbigger(j,j+1)\\ \end{Bmatrix}\hspace{1cm} otherwise \end{cases}$$

To solve the original problem, we can add a sentinel value $A[0] = −∞$ to the array and compute $LISbigger(0, 1)$.

Each recursive subproblem is identified by two indices $i$ and $j$ so there are only $O(n^2)$ distinct recursive subproblems to consider. We can memoize the results of these subproblems into a two-dimensional array ${LISbigger[0 .. n, 1 .. n]}.$ Moreover, each subproblem can be solved in $O(1)$ time, not counting recursive calls, so we should expect the final dynamic programming algorithm to run in ${O(n^2)}$ time.

The order in which the memoized recursive algorithm fills this array is not immediately clear; all we can tell from the recurrence is that each entry $LISbigger[i, j]$ is filled in after the entries $LISbigger[i, j+1]$ and $LISbigger[j, j+1]$ in the next column, as indicated on the left in the illustration below.

Fortunately, this partial information is enough to give us a valid evaluation order. If we fill the table one column at a time, from right to left, then whenever we reach an entry in the table, the entries it depends on are already available. This may not be the order that the recursive algorithm would use, but it works, so we’ll go with it. The right diagram in the illustration below illustrates this evaluation order, with a double arrow indicating the outer loop and single arrows indicating inner loops. In this case, the single arrows are bidirectional because the order that we use to fill each column doesn’t matter.