Longest Increasing Subsequence

Explore the different techniques used to solve the longest increasing subsequence problem efficiently.

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]A[1 .. n] of numbers. We developed two different recursive backtracking algorithms for this problem. Both algorithms run in O(2n)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)LISbigger(i, j), which we defined as the length of the longest increasing subsequence of A[j..n]A[ j .. n] in which every element is larger than A[i]A[i]. We derived the following recurrence for this function:

LISbigger(i,j)={ 0 if j>nLISbigger(i,j+1)if A[i]A[j]max{LISbigger(i,j+1)1+LISbigger(j,j+1)}otherwiseLISbigger(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]=A[0] = −∞ to the array and compute LISbigger(0,1)LISbigger(0, 1).

Each recursive subproblem is identified by two indices ii and jj, so there are only O(n2)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]LISbigger[0 .. n, 1 .. n]. Moreover, each subproblem can be solved in O(1)O(1) time, not counting recursive calls, so we should expect the final dynamic programming algorithm to run in O(n2){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]LISbigger[i, j] is filled in after the entries LISbigger[i,j+1]LISbigger[i, j+1] and LISbigger[j,j+1]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 the inner loop. In this case, the single arrows are bidirectional because the order that we use to fill each column doesn’t matter.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy