Longest increasing subsequence

From PEGWiki
Revision as of 01:39, 6 March 2011 by Brian (Talk | contribs) (added pseudocode)

Jump to: navigation, search

The longest increasing subsequence (LIS) problem is to find an increasing subsequence (either strictly or non-strictly) of maximum length, given a (finite) input sequence whose elements are taken from a partially ordered set. For example, consider the sequence [9,2,6,3,1,5,0,7]. An increasing subsequence is [2,3,5,7], and, in fact, there is no longer increasing subsequence. Therefore [2,3,5,7] is a longest increasing subsequence of [9,2,6,3,1,5,0,7]. The longest decreasing subsequence can be defined analogously; it is clear that a solution to one gives a solution to the other.

We will focus on the non-strict case (with some parenthetical comments about the strict case).

Discussion

There are three possible ways to state the problem:

  1. Return all longest increasing subsequences. There may be an exponential number of these; for example, consider a sequence that starts [1,0,3,2,5,4,7,6,...]; if it has length n (even) then there are 2^{n/2} increasing subsequences of length n/2 (each obtained by choosing one out of each of the pairs (1,0), (3,2), ...), and no longer increasing subsequences. Thus, this problem cannot possibly be solved efficiently.
  2. Return one longest increasing subsequence. This can be solved efficiently.
  3. Return only the maximum length that a increasing subsequence can have. This can be solved efficiently.

Reduction to LCS from non-strict case

Any increasing subsequence of a sequence is also a subsequence of the sequence sorted. For example, [9,2,6,3,1,5,0,7], when sorted, gives [0,1,2,3,5,6,7,9], and [2,3,5,7] is certainly a subsequence of this. Furthermore, if a subsequence of the original sequence is also a subsequence of the sorted sequence, then clearly it is increasing (non-strictly), and therefore an increasing subsequence of the original sequence. It follows trivially that we can compute a longest non-strictly increasing subsequence by computing a longest common subsequence of the sequence and a sorted copy of itself.

Dynamic programming solution

To compute the longest increasing subsequence contained with a given sequence x = [x_1, x_2, ..., x_n], first notice that unless x is empty, an LIS will have length at least one, and given that this is the case, it has some last element x_i. Denote the (non-empty) prefixes of x by x[1] = [x_1], x[2] = [x_1, x_2], ..., x[n] = x. Then, an LIS that ends with element x_i has the property that it is an LIS that uses the last element of x[i]. Thus, for each of the prefixes x[1], x[2], ..., x[n], we will determine an increasing subsequence that contains the last element of this prefix sequence such that no longer increasing subsequence has this property. Then, one of these must be a LIS for the original sequence.

For example, consider the sequence [9,2,6,3,1,5,0]. Its nonempty prefixes are [9], [9,2], [9,2,6], [9,2,6,3], [9,2,6,3,1], [9,2,6,3,1,5], and [9,2,6,3,1,5,0]. For each of these, we may find an increasing subsequence that uses the last element of maximal length, for example, [9], [2], [2,6], [2,3], [1], [2,3,5], and [0], respectively. The longest of these, [2,3,5], is then also an (unrestricted) LIS of the original sequence, [9,2,6,3,1,5,0,7].

Denote the LIS of x by \operatorname{LIS}(x), and denote the LIS subject to the restriction that the last element must be used as \operatorname{LIS}'(i). Then we see that |\operatorname{LIS}(x)| = \max_{1 \leq i \leq n} |\operatorname{LIS}'(i)|. We will now focus on calculating the \operatorname{LIS}' values, of which there are n (one for each nonempty prefix of x).

Optimal substructure

The dynamic substructure is not too hard to see. The value for \operatorname{LIS}'(i) consists of either:

  • the element x_i alone, which always forms an increasing subsequence by itself, or
  • the element x_i tacked on to the end of an increasing subsequence ending with x_j, where j < i and x_j \leq x_i (for the non-strict case) or x_j < x_i (for the strict case).

For example, the longest increasing subsequence that ends on the last element of [9,2,6,3,1] is just the element 1 itself, the element at the very end. But if we consider [9,2,6,3,1,5], which has as a longest increasing subsequence ending at its last element [2,3,5], we see that [2,3] is an increasing subsequence of [9,2,6,3] ending at its last element and that 3 < 5 as required.

Furthermore, it is not hard to see that the increasing subsequence we are left with after removing the last element, in the second case, must itself be optimal for the element it ends on; that is, must be a possible value of \operatorname{LIS}'(j). If this were not the case, then we would have a longer increasing subsequence ending on x_j, and then we could tack the element x_i on the end to obtain an increasing subsequence ending at x_i that is longer than the one we originally supposed was longest --- a contradiction.

Also, if we already know \operatorname{LIS}'(j) for all j < i, then one of them, when the element x_i is appended to the end, must give a LIS that ends at x_i, unless \operatorname{LIS}'(x[i]) consists of x_i only. This is because if this were not the case, then whenever we were allowed to append x_i we would obtain a suboptimal solution --- but then removing the last element from \operatorname{LIS}'(i) would give a suboptimal solution to a subinstance, which we know to be impossible.

Overlapping subproblems

When computing \operatorname{LIS}'(x[i]), we might need to know the values of \operatorname{LIS}'(x[j]) for all j < i. These are the shared subinstances; there are only n possible values in the \operatorname{LIS}' table in total.

Implementation

The optimal substructure discussed gives a very simple formula:

\operatorname{LIS}'(i) = (\text{the longest out of } (\{\operatorname{LIS}'(j) \mid 1 \leq j < i \wedge x_j \leq x_i\} \cup \{[\,]\}))x_i

(In the strict case, we have x_j < x_i strictly.)

We can easily compute this bottom-up, since we only need to know values of smaller subinstances.

The LIS of the entire sequence x is then just the largest of all \operatorname{LIS}' values.

If only the length is desired, the above formula becomes

\operatorname{LIS\_len}'(i) = 1 + \max (\{\operatorname{LIS\_len}'(j) \mid 1 \leq j < i \wedge x_j \leq x_i\} \cup \{0\})

Pseudocode

(This is for the non-strict case.)

input x
n ← length of x
for each i ∈ [1..n]
     lis[i] ← 1
     for each j ∈ [1..(i-1)]
          if x[i] ≥ x[j]
               lis[i] ← max(lis[i],1+lis[j])
return max element of lis

Analysis

Time

With the length-only formula above, computing the i^{\text{th}} entry takes O(i) time to compute, giving O(1) + O(2) + ... + O(n) = O(n^2) time overall.

This bound still holds when computing the LIS itself, but since we probably wish to avoid needless copying and concatenation of sequences, a better way is to, instead of storing the \operatorname{LIS}' values themselves in the table, simply storing their lengths as well as making a note of the next-to-last element of the sequence (or storing a zero if there is none) so that we can backtrack to reconstruct the original sequence.

Memory

\Theta(n) memory is used.

A faster algorithm

If the set from which the elements of x is taken is totally ordered, then we can do even better than this. As a matter of fact, this is usually the case, as the elements will often be integers or real numbers. This algorithm runs in O(n \log n) time, which is asymptotically optimal.[1]

The idea behind the algorithm is that if an increasing subsequence is long, then it is useful because it might give optimal subsequences that end on later elements, and if an increasing subsequence ends on a small value, then it is useful because it is versatile concerning what may be appended to the end, but if it is short and it ends on a large value, then it is not very useful. In the O(n^2) algorithm already described, a lot of time is spent looking at possibly useless increasing subsequences; for example, when computing \operatorname{LIS}'(i), we examine all values of \operatorname{LIS}'(j), where j < i, even though some x_j's may be larger than x_i.

Thus we will maintain an auxiliary array a indexed by LIS length. The entry a[i] will, at any given time, hold the least possible value for the last element of an increasing subsequence of x of length i composed of elements we have so far examined. Initially all entries of a will be set to +\infty. At the conclusion of the algorithm, the highest index at which a finite value is found is the length of the LIS.

The first thing to note is that the entries of a are (non-strictly) increasing. For example, consider the sequence [9,2,6,3,1,5,0,7]. At the conclusion of the algorithm, the array a will contain the values [0,3,5,7,+\infty,+\infty,+\infty,+\infty]. This tells us that the last element of any increasing subsequence of length 1 will be at least 0, the last element of any increasing subsequence of length 2 will be at least 3, and so on; the infinite values indicate that subsequences of those lengths do not exist. We know that a is increasing because it would be absurd if it were not. For example, suppose that a_3 < a_2, so that the least last element attainable for an increasing sequence of length 3 were less than the least last element attainable for an increasing sequence of length 2. Then we could remove the last element from the sequence of length 3 to obtain an even smaller element (possibly) at the end of an increasing sequence of length 2, which contradicts the optimality of the value we already have on file.

Now let's see how the array a allows us to find the length of the LIS. We consider the elements of x one at a time starting from x_1. For each element x_i we consider, we notice that we want to find the longest increasing subsequence so far discovered that ends on a value less than or equal to x_i. To do this, we perform a binary search on the array a for the largest index j for which a_j \leq x_i, or return j=0 if no such index exists (empty sequence). Then, we know we can obtain an increasing subsequence of length j+1 by appending x_i to the end of the increasing subsequence of length j ending at on value a_j; if there is no such value then we get an increasing subsequence of length 1 by taking x_i by itself. What effect does this have on a? We know that x_i < a_{j+1}, and we also know that we have obtained an increasing subsequence of length j+1 whose last element is x_i, which is therefore better than what we have on file for a_{j+1}. Therefore, we update a_{j+1} so that it equals x_i. Note that after this operation, a will still be sorted, because x_i was originally less than a_{j+2}, so a_{j+1} will be less after the update, and a_{j+1} will still be greater than or equal to a_j, because x_i \geq a_j. After iterating through all elements of x and updating a at each step, the algorithm terminates.

Pseudocode

(Non-strict case.)

input x
n ← length of x
result ← 0
a[0] ← -∞
for each i ∈ [1..n]
     a[i] ← +∞
for each i ∈ [1..n]
     l ← 0
     u ← n
     while u > l
          if a[⌊(l+u)/2⌋] ≤ x[i]
               l ← 1 + ⌊(l+u)/2⌋
          else
               u ← ⌊(l+u)/2⌋
     a[l] ← x[i]
     result ← max(result,l)
return result

Analysis

The reason why we expect this algorithm to be more efficient is that, by examining only a instead of the preceding x-values, all the irrelevant increasing subsequences (the ones that are both short and high at the end) are ignored, as they cannot "win" on either front and hence secure a position in a.

Time

The time taken for a binary search in the auxiliary array, of size n, is O(\log n), and one is executed as each element of x is examined. Therefore this algorithm achieves the stated time bound of O(n \log n).

Memory

Still O(n), as our auxiliary array has size n.

References

  1. Fredman, Michael L. (1975), "On computing the length of longest increasing subsequences", Discrete Mathematics 11 (1): 29–35, doi:10.1016/0012-365X(75)90103-X