Longest increasing subsequence - Revision history

162.158.93.101: /* Pseudocode */

2018-06-10T11:10:27Z

‎Pseudocode

162.158.93.101: /* Pseudocode */

2018-06-10T11:08:48Z

‎Pseudocode

84.228.139.57: /* Optimal substructure */

2016-01-18T18:33:42Z

‎Optimal substructure

Brian: added pseudocode

2011-03-06T01:39:17Z

added pseudocode

Brian at 00:27, 3 March 2011

2011-03-03T00:27:25Z

Brian: Created page with "The '''longest increasing subsequence''' (LIS) problem is to find an increasing subsequence (either strictly or non-strictly) of maximum length, given..."

2011-03-02T21:58:50Z

Created page with "The '''longest increasing subsequence''' (LIS) problem is to find an increasing subsequence (either strictly or non-strictly) of maximum length, given..."

New page

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.

==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 <math>n</math> (even) then there are <math>2^{n/2}</math> increasing subsequences of length <math>n/2</math> (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 <math>x = [x_1, x_2, ..., x_n]</math>, first notice that unless <math>x</math> is empty, an LIS will have length at least one, and given that this is the case, it has some last element <math>x_i</math>. Denote the (non-empty) prefixes of <math>x</math> by <math>x[1] = [x_1], x[2] = [x_1, x_2], ..., x[n] = x</math>. Then, an LIS that ends with element <math>x_i</math> has the property that it is an LIS that uses the last element of <math>x[i]</math>. Thus, for each of the prefixes <math>x[1], x[2], ..., x[n]</math>, 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 <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>).

==Optimal substructure==

[[Category:Dynamic programming]]

@@ Line 52: / Line 52: @@
 for each i &isin; [1..n]
       lis[i] &larr; 1
-for each j &isin; [1..(i-1)]
+     for each j &isin; [1..(i-1)]
-     if x[i] &ge; x[j]
+          if x[i] &ge; x[j]
-     lis[i] &larr; max(lis[i],1+lis[j])
+          lis[i] &larr; max(lis[i],1+lis[j])
 return max element of lis
 </pre>

@@ Line 52: / Line 52: @@
 for each i &isin; [1..n]
       lis[i] &larr; 1
-     for each j &isin; [1..(i-1)]
+for each j &isin; [1..(i-1)]
-          if x[i] &ge; x[j]
+     if x[i] &ge; x[j]
-               lis[i] &larr; max(lis[i],1+lis[j])
+     lis[i] &larr; max(lis[i],1+lis[j])
 return max element of lis
 </pre>

@@ Line 20: / Line 20: @@
 ===Optimal substructure===
-The dynamic substructure is not too hard to see. The value for <math>\operatorname{LIS}'(i)</math> consists of either:
+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).

@@ Line 42: / Line 42: @@
 The LIS of the entire sequence <math>x</math> is then just the largest of all <math>\operatorname{LIS}'</math> values.
 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.
@@ Line 63: / Line 77: @@
 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===

@@ 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.
 ==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==
+====Memory====
 [[Category:Dynamic programming]]