Difference between revisions of "Longest increasing subsequence"

Revision as of 00:27, 3 March 2011

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:

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.
Return one longest increasing subsequence. This can be solved efficiently.
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.

Analysis

Time

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\})

Thus, 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.

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

↑ 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

[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

[1]

@@ Line 1: / Line 1: @@
-The '''longest increasing subsequence''' (LIS) problem is to find an [[subsequence#Definitions|increasing subsequence]] (either strictly or non-strictly) of maximum length, given an input sequence whose elements belong 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.
+The '''longest increasing subsequence''' (LIS) problem is to find an [[subsequence#Definitions|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==
@@ Line 15: / Line 17: @@
 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 <math>x</math> by <math>\operatorname{LIS}(x)</math>, and denote the LIS subject to the restriction that the last element must be used as <math>\operatorname{LIS}'(x[i])</math>. Then we see that <math>|\operatorname{LIS}(x)| = \max_{1 \leq i \leq n} |\operatorname{LIS}'(x[i])|</math>. We will now focus on calculating the <math>\operatorname{LIS}'</math> values, of which there are <math>n</math> (one for each nonempty prefix of <math>x</math>).
+Denote the LIS of <math>x</math> by <math>\operatorname{LIS}(x)</math>, and denote the LIS subject to the restriction that the last element must be used as <math>\operatorname{LIS}'(i)</math>. Then we see that <math>|\operatorname{LIS}(x)| = \max_{1 \leq i \leq n} |\operatorname{LIS}'(i)|</math>. We will now focus on calculating the <math>\operatorname{LIS}'</math> values, of which there are <math>n</math> (one for each nonempty prefix of <math>x</math>).
+===Optimal substructure===
+The dynamic substructure is not too hard to see. The value for <math>\operatorname{LIS}'(i)</math> consists of either:
+* the element <math>x_i</math> alone, which always forms an increasing subsequence by itself, or
+* the element <math>x_i</math> tacked on to the end of an increasing subsequence ending with <math>x_j</math>, where <math>j < i</math> and <math>x_j \leq x_i</math> (for the non-strict case) or <math>x_j < x_i</math> (for the strict case).
+For example, the longest increasing subsequence that ends on the last element of <math>[9,2,6,3,1]</math> is just the element <math>1</math> itself, the element at the very end. But if we consider <math>[9,2,6,3,1,5]</math>, which has as a longest increasing subsequence ending at its last element <math>[2,3,5]</math>, we see that <math>[2,3]</math> is an increasing subsequence of <math>[9,2,6,3]</math> ending at ''its'' last element and that <math>3 < 5</math> 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 <math>\operatorname{LIS}'(j)</math>. If this were not the case, then we would have a longer increasing subsequence ending on <math>x_j</math>, and then we could tack the element <math>x_i</math> on the end to obtain an increasing subsequence ending at <math>x_i</math> that is longer than the one we originally supposed was longest --- a contradiction.
+Also, if we already know <math>\operatorname{LIS}'(j)</math> for all <math>j < i</math>, then one of them, when the element <math>x_i</math> is appended to the end, must give a LIS that ends at <math>x_i</math>, unless <math>\operatorname{LIS}'(x[i])</math> consists of <math>x_i</math> only. This is because if this were not the case, then whenever we were allowed to append <math>x_i</math> we would obtain a suboptimal solution --- but then removing the last element from <math>\operatorname{LIS}'(i)</math> would give a suboptimal solution to a subinstance, which we know to be impossible.
+===Overlapping subproblems===
+When computing <math>\operatorname{LIS}'(x[i])</math>, we might need to know the values of <math>\operatorname{LIS}'(x[j])</math> for all <math>j < i</math>. These are the shared subinstances; there are only <math>n</math> possible values in the <math>\operatorname{LIS}'</math> table in total.
+===Implementation===
+The optimal substructure discussed gives a very simple formula:
+:<math>\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</math>
+(In the strict case, we have <math>x_j < x_i</math> strictly.)
+We can easily compute this bottom-up, since we only need to know values of smaller subinstances.
+The LIS of the entire sequence <math>x</math> is then just the largest of all <math>\operatorname{LIS}'</math> values.
+===Analysis===
+====Time====
+If only the length is desired, the above formula becomes
+:<math>\operatorname{LIS\_len}'(i) = 1 + \max (\{\operatorname{LIS\_len}'(j) \mid 1 \leq j < i \wedge x_j \leq x_i\} \cup \{0\})</math>
+Thus, computing the <math>i^{\text{th}}</math> entry takes <math>O(i)</math> time to compute, giving <math>O(1) + O(2) + ... + O(n) = O(n^2)</math> 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 <math>\operatorname{LIS}'</math> 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====
+<math>\Theta(n)</math> memory is used.
+==A faster algorithm==
+If the set from which the elements of <math>x</math> 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 <math>O(n \log n)</math> time, which is asymptotically optimal.<ref>Fredman, Michael L. (1975), "On computing the length of longest increasing subsequences", ''Discrete Mathematics'' '''11''' (1): 29–35, [http://dx.doi.org/10.1016%2F0012-365X%2875%2990103-X doi:10.1016/0012-365X(75)90103-X]</ref>
+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 <math>O(n^2)</math> algorithm already described, a lot of time is spent looking at possibly useless increasing subsequences; for example, when computing <math>\operatorname{LIS}'(i)</math>, we examine all values of <math>\operatorname{LIS}'(j)</math>, where <math>j < i</math>, even though some <math>x_j</math>'s may be larger than <math>x_i</math>.
+Thus we will maintain an auxiliary array <math>a</math> indexed by LIS length. The entry <math>a[i]</math> will, at any given time, hold the least possible value for the last element of an increasing subsequence of <math>x</math> of length <math>i</math> composed of elements we have so far examined. Initially all entries of <math>a</math> will be set to <math>+\infty</math>. 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 <math>a</math> are (non-strictly) increasing. For example, consider the sequence <math>[9,2,6,3,1,5,0,7]</math>. At the conclusion of the algorithm, the array <math>a</math> will contain the values <math>[0,3,5,7,+\infty,+\infty,+\infty,+\infty]</math>. 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 <math>a</math> is increasing because it would be absurd if it were not. For example, suppose that <math>a_3 < a_2</math>, 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 <math>a</math> allows us to find the length of the LIS. We consider the elements of <math>x</math> one at a time starting from <math>x_1</math>. For each element <math>x_i</math> 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 <math>x_i</math>''. To do this, we perform a [[binary search]] on the array <math>a</math> for the largest index <math>j</math> for which <math>a_j \leq x_i</math>, or return <math>j=0</math> if no such index exists (empty sequence). Then, we know we can obtain an increasing subsequence of length <math>j+1</math> by appending <math>x_i</math> to the end of the increasing subsequence of length <math>j</math> ending at on value <math>a_j</math>; if there is no such value then we get an increasing subsequence of length 1 by taking <math>x_i</math> by itself. What effect does this have on <math>a</math>? We know that <math>x_i < a_{j+1}</math>, and we also know that we have obtained an increasing subsequence of length <math>j+1</math> whose last element is <math>x_i</math>, which is therefore ''better'' than what we have on file for <math>a_{j+1}</math>. Therefore, we update <math>a_{j+1}</math> so that it equals <math>x_i</math>. Note that after this operation, ''<math>a</math> will still be sorted'', because <math>x_i</math> was originally less than <math>a_{j+2}</math>, so <math>a_{j+1}</math> will be less after the update, and <math>a_{j+1}</math> will still be greater than or equal to <math>a_j</math>, because <math>x_i \geq a_j</math>. After iterating through all elements of <math>x</math> and updating <math>a</math> at each step, the algorithm terminates.
+===Analysis===
+The reason why we expect this algorithm to be more efficient is that, by examining only <math>a</math> instead of the preceding <math>x</math>-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 <math>a</math>.
+====Time====
+The time taken for a binary search in the auxiliary array, of size <math>n</math>, is <math>O(\log n)</math>, and one is executed as each element of <math>x</math> is examined. Therefore this algorithm achieves the stated time bound of <math>O(n \log n)</math>.
-==Optimal substructure==
+====Memory====
+Still <math>O(n)</math>, as our auxiliary array has size <math>n</math>.
+==References==
+<references/>
 [[Category:Dynamic programming]]

Difference between revisions of "Longest increasing subsequence"

Revision as of 00:27, 3 March 2011

Contents

Discussion

Reduction to LCS from non-strict case

Dynamic programming solution

Optimal substructure

Overlapping subproblems

Implementation

Analysis

Time

Memory

A faster algorithm

Analysis

Time

Memory

References

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools