In computer science, the longest increasing subsequence problem is to find a subsequence
of a given sequence in which the subsequence's elements are in sorted order, lowest to highest,
and in which the subsequence is as long as possible. This subsequence is not necessarily
contiguous, or unique. Longest increasing subsequences are studied in the context of
various disciplines related to mathematics, including algorithmics, random matrix theory,
representation theory, and physics. The longest increasing subsequence problem is solvable
in time O(n log n), where n denotes the length of the input sequence.
Example In the first 16 terms of the binary Van der
Corput sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3,
11, 7, 15 a longest increasing subsequence is
0, 2, 6, 9, 13, 15. This subsequence has length six; the input
sequence has no seven-member increasing subsequences. The longest increasing subsequence in this
example is not unique: for instance, 0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing subsequences of equal length in the same input sequence.
Relations to other algorithmic problems The longest increasing subsequence problem
is closely related to the longest common subsequence problem, which has a quadratic time dynamic
programming solution: the longest increasing subsequence of a sequence S is the longest
common subsequence of S and T, where T is the result of sorting S. However, for the
special case in which the input is a permutation of the integers 1, 2, ..., n, this approach
can be made much more efficient, leading to time bounds of the form O(n log log n).
The largest clique in a permutation graph is defined by the longest decreasing subsequence
of the permutation that defines the graph; the longest decreasing subsequence is equivalent
in computational complexity, by negation of all numbers, to the longest increasing subsequence.
Therefore, longest increasing subsequence algorithms can be used to solve the clique
problem efficiently in permutation graphs. In the Robinson–Schensted correspondence
between permutations and Young tableaux, the length of the first row of the tableau corresponding
to a permutation equals the length of the longest increasing subsequence of the permutation,
and the length of the first column equals the length of the longest decreasing subsequence.
Efficient algorithms The algorithm outlined below solves the longest
increasing subsequence problem efficiently with arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing subsequence found so
far. Denote the sequence values as X[0], X[1], etc. Then, after processing X[i], the algorithm
will have stored values in two arrays: M[j] — stores the index k of the smallest
value X[k] such that there is an increasing subsequence of length j ending at X[k] on
the range k ≤ i. P[k] — stores the index of the predecessor
of X[k] in the longest increasing subsequence ending at X[k].
In addition the algorithm stores a variable L representing the length of the longest increasing
subsequence found so far. Because the algorithm below uses zero-based numbering, for clarity
we pad M with M[0], which goes unused so that M[j] corresponds to a subsequence of length
j. A real implementation can skip M[0] and adjust the indices accordingly.
Note that, at any point in the algorithm, the sequence
X[M[1]], X[M[2]], ..., X[M[L]] is nondecreasing. For, if there is an increasing
subsequence of length i ending at X[M[i]], then there is also a subsequence of length
i-1 ending at a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do
binary searches in this sequence in logarithmic time.
The algorithm, then, proceeds as follows:
P = array of length N M = array of length N + 1
L = 0 for i in range 0 to N-1:
Binary search for the largest positive j ≤ L such that X[M[j]] < X[i]
lo = 1 hi = L
while lo ≤ hi: mid =/2
if X[M[mid]] < X[i]: lo = mid+1
else: hi = mid-1
After searching, lo is 1 greater than the length of the longest prefix of X[i]
newL = lo
The predecessor of X[i] is the last index of
the subsequence of length newL-1 P[i] = M[newL-1]
M[newL] = i
if newL > L: If we found a subsequence longer than any
we've found yet, update L
L = newL
Reconstruct the longest increasing subsequence S = array of length L
k = M[L] for i in range L-1 to 0:
S[i] = X[k] k = P[k]
return S
Because the algorithm performs a single binary search per sequence element, its total time
can be expressed using Big O notation as O(n log n). Fredman discusses a variant of this algorithm,
which he credits to Donald Knuth; in the variant that he studies, the algorithm tests whether
each value X[i] can be used to extend the current longest increasing sequence, in constant
time, prior to doing the binary search. With this modification, the algorithm uses at most
n log2 n − n log2log2 n + O(n) comparisons in the worst case, which is optimal for a
comparison-based algorithm up to the constant factor in the O(n) term.
Length bounds According to the Erdős–Szekeres theorem,
any sequence of n2+1 distinct integers has either an increasing or a decreasing subsequence
of length n + 1. For inputs in which each permutation of the input is equally likely,
the expected length of the longest increasing subsequence is approximately 2√n. In the
limit as n approaches infinity, the length of the longest increasing subsequence of a
randomly permuted sequence of n items has a distribution approaching the Tracy–Widom
distribution, the distribution of the largest eigenvalue of a random matrix in the Gaussian
unitary ensemble. Online algorithms
The longest increasing subsequence has also been studied in the setting of online algorithms,
in which the elements of a permutation are presented one at a time to an algorithm that
must decide whether to include or exclude each element, without knowledge of the ordering
of later elements. In this variant of the problem, it is possible to devise a selection
procedure that, when given a random permutation as input, will generate an increasing sequence
with expected length approximately √(2n). Variance bounds have also been studied, but
exact variance asymptotics and limit theorems are still open. More precise results are known
for the corresponding problem in the setting of a Poisson arrival process.
See also Patience sorting, an efficient technique for
finding the length of the longest increasing subsequence
Plactic monoid, an algebraic system defined by transformations that preserve the length
of the longest increasing subsequence Anatoly Vershik, a Russian mathematician who
studied applications of group theory to longest increasing subsequences
Longest common subsequence Longest alternating subsequence
References
External links Algorithmist's Longest Increasing Subsequence
Explanation on Geeksforgeeks