Longest Increasing Subsequence

From Algorithmist

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.

Contents 1 Overview 2 Techniques 2.1 Longest Common Subsequence 2.2 Dynamic Programming 2.3 Faster Algorithm 3 Implementation

[edit] Overview

Formally, the problem is as follows:

Given a sequence , find the largest subset such that for every i < j, a_i < a_j.

[edit] Techniques

[edit] Longest Common Subsequence

A simple way of finding the longest increasing subsequence is to use the Longest Common Subsequence (Dynamic Programming) algorithm.

1. Make a sorted copy of the sequence A, denoted as B. O(nlg(n)) time.
2. Use Longest Common Subsequence on with A and B. O(n²) time.

[edit] Dynamic Programming

There is a straight-forward Dynamic Programming solution in O(n²) 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 , 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 new number (a_{k + 1}) is lower than the last number of the subsequence (a_k) and greater than the second last (a_{k - 1}). In this case the last number of the subsequence (a_k) is replaced by the new number (a_{k + 1}).
• The new number (a_{k + 1}) is greater than the last number (a_k) of the subsequence: The new number (a_{k + 1}) 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 )

[edit] Faster Algorithm

There's also an O(nlogn) solution based on some observations. Let A_i,j be the smallest possible tail out of all increasing subsequences of length j using elements .

Observe that, for any particular i, . 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 A_i,j < a_{i + 1} < = A_{i,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 A_i,k for .

Furthermore, there is at most one difference between the set A_i and the set A_{i + 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 .

[edit] Implementation

• C
• C++ (O(nlogn) algorithm - output sensitive - O(nlogk))