Longest increasing subsequence problem

The longest increasing subsequence problem is to find the longest increasing subsequence of a given sequence. It also reduces to a graph theory problem of finding the longest path in a directed acyclic graph.

Overview

Formally, the problem is as follows:

Given a sequence $a_{0},a_{1},a_{2},\ldots ,a_{n}$, find the longest subset such that for every $i<j$, $a_{i}<a_{j}$.

Techniques

Longest Common Subsequence

A simple way of finding the longest increasing subsequence is to use the longest-common subsequence problem (dynamic programming) algorithm.

1. Make a sorted copy of the sequence $A$, denoted as $B$. $O(n\lg(n))$ time.
2. Use longest-common subsequence problem on with $A$ and $B$. $O(n^{2})$ time.

Dynamic Programming

There is a straight-forward dynamic programming solution in $O(n^{2})$ time. Though this is asymptotically equivalent to the longest common subsequence version of the solution, the constant is lower, as there is less overhead.

Given the sequence $a_{0},a_{1},a_{2},\ldots ,a_{k}$, the optimal way to add $a_{k}+1$ would simply be the longest of the longest subsequence from $a_{i}$ to $a_{k}+1$, adding it to each list if needed. For each $a_{k}+1$, there are two possibilities:

• The number is lower than the last number of the subsequence and greater than the second last. In this case the last number of the subsequence is replaced by the new number.
• The number is greater than the last number of the subsequence: The number is appended to the subsequence and if this subsequence is the best subsequence with this length, it will be stored.

The pseudo-code is show below:

func lis( a )
   initialize best to an array of 0's.
   for ( i from 1 to n )
      best[i] = 1
      for ( j from 1 to i - 1 )
         if ( a[i] > a[j] )
            best[i] = max( best[i], best[j] + 1 )
   return max( best )

There's also an $O(n\lg {n})$ solution based on some observations. Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a1, a2, a3, …, ai.

Observe that, for any particular i, Ai,1 < Ai,2 < … < Ai,j. This suggests that if we want the longest subsequence that ends with a(i+1), we only need to look for a j such that Ai,j < a(i+1) <= Ai,j+1 and the length will be (j+1).

Notice that in this case, A(i+1,j+1) will be equal to a(i+1), and all A(i+1, k) will be equal to Ai,k for k != j + 1.

Furthermore, there is at most one difference between the set Ai and the set Ai+1, which is caused by this search.

Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a1, a2, …, an.