Editing Longest increasing subsequence

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]]