Longest increasing subsequence

The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics.

[1][2] The longest increasing subsequence problem is solvable in time

[3] In the first 16 terms of the binary Van der Corput sequence one of the longest increasing subsequences is This subsequence has length six; the input sequence has no seven-member increasing subsequences.

The longest increasing subsequence in this example is not the only solution: for instance, are other increasing subsequences of equal length in the same input sequence.

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

However, for the special case in which the input is a permutation of the integers

this approach can be made much more efficient, leading to time bounds of the form

[4] The largest clique in a permutation graph corresponds to the longest decreasing subsequence of the permutation that defines the graph (assuming the original non-permuted sequence is sorted from lowest value to highest).

Similarly, the maximum independent set in a permutation graph corresponds to the longest non-decreasing subsequence.

Therefore, longest increasing subsequence algorithms can be used to solve the clique problem efficiently in permutation graphs.

[5] 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.

[3] 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.

and values in two arrays: Because the algorithm below uses zero-based numbering, for clarity

Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows: Because the algorithm performs a single binary search per sequence element, its total time can be expressed using Big O notation as

Fredman (1975) discusses a variant of this algorithm, which he credits to Donald Knuth; in the variant that he studies, the algorithm tests whether each value

can be used to extend the current longest increasing sequence, in constant time, prior to doing the binary search.

comparisons in the worst case, which is optimal for a comparison-based algorithm up to the constant factor in the

distinct integers has an increasing or a decreasing subsequence of length

[7][8] For inputs in which each permutation of the input is equally likely, the expected length of the longest increasing subsequence is approximately

approaches infinity, the Baik-Deift-Johansson theorem says, that the length of the longest increasing subsequence of a randomly permuted sequence of

[10] The longest increasing subsequence has also been studied in the setting of online algorithms, in which the elements of a sequence of independent random variables with continuous distribution

In this variant of the problem, which allows for interesting applications in several contexts, it is possible to devise an optimal selection procedure that, given a random sample of size

as input, will generate an increasing sequence with maximal expected length of size approximately

[11] The length of the increasing subsequence selected by this optimal procedure has variance approximately equal to

and its limiting distribution is asymptotically normal after the usual centering and scaling.

[12] The same asymptotic results hold with more precise bounds for the corresponding problem in the setting of a Poisson arrival process.

[13] A further refinement in the Poisson process setting is given through the proof of a central limit theorem for the optimal selection process which holds, with a suitable normalization, in a more complete sense than one would expect.

The proof yields not only the "correct" functional limit theorem but also the (singular) covariance matrix of the three-dimensional process summarizing all interacting processes.