Longest Increasing Subsequence

From Algorithmist
Jump to: navigation, search

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

[edit] Overview

Formally, the problem is as follows:

Given a sequence a_1, a_2, \ldots, a_n, find the largest subset such that for every i < j, ai < aj.

[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(nlog(n)) time.
  2. Use Longest Common Subsequence on with A and B. O(n2) time.

[edit] Dynamic Programming

There is a straight-forward Dynamic Programming solution in O(n2) time. Though this is asymptotically equivalent to the Longest Common Subsequence version of the solution, the constant is lower, as there is less overhead.

Let A be our sequence a_1,a_2,\ldots,a_n. Define qk as the length of the longest increasing subsequence of A, subject to the constraint that the subsequence must end on the element ak. The longest increasing subsequence of A must end on some element of A, so that we can find its length by searching for the maximum value of q. All that remains is to find out the values qk.

But qk can be found recursively, as follows: consider the set Sk of all i < k such that ai < ak. If this set is null, then all of the elements that come before ak are greater than it, which forces qk = 1. Otherwise, if Sk is not null, then q has some distribution over Sk. By the general contract of q, if we maximize q over Sk, we get the length of the longest increasing subsequence in Sk; we can append ak to this sequence, to get that:

q_k = max(q_j | j \isin S_k) + 1

If the actual subsequence is desired, it can be found in O(n) further steps by moving backward through the q-array, or else by implementing the q-array as a set of stacks, so that the above "+ 1" is accomplished by "pushing" ak into a copy of the maximum-length stack seen so far.

Some pseudo-code for finding the length of the longest increasing subsequence:

function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

[edit] Faster Algorithm

There's also an O(nlogn) solution based on some observations. Let Ai,j be the smallest possible tail out of all increasing subsequences of length j using elements a_1, a_2, a_3, \ldots, a_i.

Observe that, for any particular i, A_{i,1} < A_{i,2} < \ldots < A_{i,j}. This suggests that if we want the longest subsequence that ends with ai + 1, we only need to look for a j such that Ai,j < ai + 1 < = Ai,j + 1 and the length will be j + 1.

Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + 1,k will be equal to Ai,k for k \ne 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 a_1, a_2, \ldots, a_n.

Further explain:--GONG Zhi Tao 11:19, 1 August 2012 (EDT)

We have elements: a_1, a_2, a_3, \ldots, a_i.

And we have a longest increasing subsequences of them: A_{i,1} < A_{i,2} < \ldots < A_{i,j}, for any Ai,k(1 < = k < = j) you could not find a smaller alternative.

Now we have a new element: ai + 1

What we can do about it:

1. insert it at the back if Ai,j < ai + 1, where we will have a longer one;

2. make it an alternative for Ai,k if A_{i,k-1} < a_{i+1}\ AND\ a_{i+1} <= A_{i,k}

Alternative means that we MIGHT get longer ones if using the new element.

[edit] Implementation

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

[edit] Other Resources

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox