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)$ ...