↑ arvau

Wikipedia / Longest increasing subsequence

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. denotes the length of the input sequence.

Example

In the first 16 terms of the binary Van der Corput sequence

  1. 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

one of the longest increasing subsequences is

  1. 0, 2, 6, 9, 11, 15.

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,

  1. 0, 4, 6, 9, 11, 15

  2. 0, 2, 6, 9, 13, 15

  3. 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 is the result of sorting

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.

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 and values in two arrays:

  • — stores the length of the longest increasing subsequence found so far.

is the largest one.

  • represents the index of its termination.

  • can be any value).

  • can be any value).

Because the algorithm below uses zero-based numbering and adjust the indices accordingly.

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
M[0] = -1 // undefined so can be set to any value

L = 0
for i in range 0 to N-1: //N-1 included
    // Binary search for the smallest positive l ≤ L
    // such that X[M[l]] >= X[i]
    lo = 1
    hi = L + 1
    while lo < hi:
        mid = lo + floor((hi-lo)/2) // lo <= mid < hi
        if X[M[mid]] >= X[i]
            hi = mid
        else: // if X[M[mid]] < X[i]
            lo = mid + 1

    // After searching, lo == hi 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
// It consists of the values of X at the L indices:
// ...,  P[P[M[L]]], P[M[L]], M[L]
S = array of length L
k = M[L]
for j in range L-1 to 0: //0 included
    S[j] = 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 discusses a variant of this algorithm, which he credits to Donald Knuth term.

Example run

Length bounds

According to the Erdős–Szekeres theorem

approaches infinity, the Baik-Deift-Johansson theorem 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 sequence of independent random variables – or alternatively the elements of a random permutation and its limiting distribution is asymptotically normal after the usual centering and scaling. The same asymptotic results hold with more precise bounds for the corresponding problem in the setting of a Poisson arrival process. 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.

See also

References