Longest increasing subsequence
Encyclopedia
The longest increasing subsequence problem is to find a subsequence of a given sequence
in which the subsequence 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.
a longest increasing subsequence is
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,
is another increasing subsequence of equal length in the same input sequence.
, 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.
It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:
In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.
Note that, at any point in the algorithm, the sequence
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.
L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)
The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form
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). 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 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 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 algorithm
s, 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).
More precise results (including the variance) are known for the corresponding problem in the setting of a Poisson arrival process.
See also
External links
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
in which the subsequence 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
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, including algorithmics, random matrix theory, representation theory
Representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...
, and physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
. 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 binary Van der Corput sequenceVan der Corput sequence
A van der Corput sequence is a low-discrepancy sequence over the unit interval first published in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base n representation of the sequence of natural numbers...
- 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
is another increasing subsequence 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 problemLongest common subsequence problem
The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences . Note that subsequence is different from a substring, see substring vs. subsequence...
, which has a quadratic time dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
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
Sorting
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:# ordering: arranging items of the same kind, class, nature, etc...
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
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
in a permutation graph
Permutation graph
In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...
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
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
efficiently in permutation graphs.
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence problem efficiently, using only 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[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:
- M[j] — stores the position 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 (note we have j ≤ k ≤ i here).
- P[k] — stores the position 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.
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.
L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)
The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form
- ..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].
Because the algorithm performs a single binary search per sequence element, its total time can be expressed using Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
as O(n log n). discusses a variant of this algorithm, which he credits to Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
; 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 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
Erdos–Szekeres theorem
In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every sequence of distinct real numbers contains either a monotonically increasing infinite subsequence, or a...
, any sequence of n2+1 distinct integers has either an increasing or a decreasing subsequence of length 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
Tracy–Widom distribution
The Tracy–Widom distribution, introduced by , is the probability distribution of the largest eigenvalue of a random hermitian matrix in the edge scaling limit. It also appears in the distribution of the length of the longest increasing subsequence of random permutations and in current fluctuations...
, 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 algorithm
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
s, 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).
More precise results (including the variance) are known for the corresponding problem in the setting of a Poisson arrival process.
See also
- Patience sortingPatience sortingPatience sorting is a sorting algorithm, based on a solitaire card game, that has the property of being able to efficiently compute the length of a longest increasing subsequence in a given array.-The card game:...
, an efficient technique for finding the length of the longest increasing subsequence - Plactic monoidPlactic monoidIn mathematics, the plactic monoid is the monoid of all words in the alphabet of positive integers modulo Knuth equivalence. Its elements can be identified with semistandard Young tableaux...
, an algebraic system defined by transformations that preserve the length of the longest increasing subsequence - Anatoly VershikAnatoly VershikAnatoly Moiseevich Vershik is a Soviet and Russian mathematician. He is most famous for his joint work with Sergey V. Kerov on representations of infinite symmetric groups and applications to the longest increasing subsequences....
, a Russian mathematician who studied applications of group theory to longest increasing subsequences
External links