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. In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. ... A diagram of a graph with 6 vertices and 7 edges. ... A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...

Overview

Formally, the problem is as follows:

Given a sequence , 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. The longest-common subsequence problem is the search for an efficient method of finding the longest common subsequence (LCS). ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...

1. Make a sorted copy of the sequence A, denoted as B. O(nlg(n)) time.
2. Use longest-common subsequence problem on with A and B. O(n²) time.

Sorting refers to a process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings: ordering: aranging items of the same kind, class, nature, etc. ... The longest-common subsequence problem is the search for an efficient method of finding the longest common subsequence (LCS). ...

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. In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... The longest-common subsequence problem is the search for an efficient method of finding the longest common subsequence (LCS). ...

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 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(nlgn) 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 .

External Links

Algorithmist's Longest Increasing Subsequence - Where this article was taken.