Jump to content

Longest increasing subsequence problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Vkarpov15 (talk | contribs) at 02:01, 28 October 2006 (Relations to other algorithmic problems). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The longest increasing subsequence problem is to find the longest increasing subsequence of a given sequence. Note that subsequence we are searching for is not necessarily contiguous. Searching for the longest contiguous increasing subsequence would be a simple matter of scanning the whole sequence to find the points where the values decrease, and taking the longest gap between two such points.

The longest increasing subsequence problem has long been known to be solvable in time O(n log n) (Schensted 1961).

Relations to other algorithmic problems

The longest increasing subsequence problem is closely related to the longest common subsequence problem, which has a quadratic time dynamic programming solution: the longest increasing subsequence of a sequence S is the longest common subsequence of S and T, where T is the result of sorting S. However, for the special case in which the input is a permutation of the integers 1, 2, ..., n, this approach can be made much more efficient, leading to time bounds of the form O(n log log n) (Hunt and Szymanski 1977).

The longest increasing subsequence problem can also be related to finding the longest path in a directed acyclic graph derived from the input sequence: we construct a vertex per sequence value and connect values x and y by an edge when x is both smaller than y and occurs earlier than it in the sequence. Longest paths in DAGs can be found in time linear in the size of the DAG, but in this case the size can be quadratic in the sequence length, so this algorithm is not asymptotically faster than the dynamic programming one.

Algorithm

Say we have a sequence of numbers of length N. Define an array bestLength[] of length N, where bestLength[i] represents the length of the longest increasing subsequence which ends at the i-th number in the sequence. Obviously bestLength[0]=1. Next we'll define a simple recurrence relationship; obviously bestLength[i]=bestLength[j]+1 for some j such that sequence[j] is less than sequence[i] and j is less than i. Since we want the longest increasing subsequence, we'll simply find the largest value of bestLength[j] which satisfies the above condition. If there are no j which satisfy the above condition, then bestLength[i] is obviously 1 because the subsequence containing simply sequence[i] is also an increasing subsequence.

The actual code looks like this:

  int bestLength[]=new int[N];
  //All bestLength values are initially 0.
  bestLength[0]=1;
  for(int i=1...N-1) {
     for(int j=0...i-1) {
       if(sequence[i] greater than sequence[j] & bestLength[j]+1 greater than bestLength[i]) bestLength[i]=bestLength[j]+1;
     }
     if(bestLength[i]==0) bestLength[i]=1;
  }

This is a classic example of Dynamic Programming. If you need to find the numbers in the longest increasing subsequences, simply maintain an array called lastIndex[] of length N for which lastIndex[i] is the value of j which satisfies the conditions in the first paragraph and if bestLength[i]==1 then lastIndex[i]=i. Thus if curIndex is initially the index for which bestLength[curIndex] has the highest value;

    int longestSubsequence[]=new int[bestLength[curIndex]];
    for(int i=0...bestLength[curIndex]-1) {
       longestSubsequence[bestLength[curIndex]-i-1]=sequence[curIndex];
       curIndex=lastIndex[curIndex];
    }

So we simply go backwards and add every number to the longestSubsequence array in reverse order.

See also

References

  • Hunt, J.; Szymanski, T. (1977). "A fast algorithm for computing longest common subsequences". Communications of the ACM: 350–353.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  • Schensted, C. (1961). "Longest increasing and decreasing subsequences". Canadian Journal of Mathematics. 13: 179–191.