Longest increasing subsequence
The longest increasing subsequence (LIS) of a given sequence of distinct real numbers is the subsequence of maximum length in which the elements appear in strictly increasing order while preserving their relative positions from the original sequence.[1] This concept is fundamental in combinatorics and algorithmics, serving as a measure of ordered structure within sequences and underpinning problems in pattern recognition, sorting theory, and statistical analysis of permutations.[2]
The study of LIS originated in the 1935 Erdős–Szekeres theorem, which proves that any sequence of more than (r-1)(s-1) distinct real numbers must contain either a strictly increasing subsequence of length r or a strictly decreasing subsequence of length s, providing a foundational result on the inevitability of monotonic patterns in sufficiently long sequences.[3] Building on this, C. Schensted's 1961 work introduced the Robinson–Schensted correspondence, a bijection between permutations and pairs of standard Young tableaux that equates the length of the LIS to the length of the longest row in the insertion tableau, thus connecting the problem to representation theory and partition combinatorics.[1] Subsequent developments, including patience sorting—a greedy algorithm for partitioning sequences into piles—further illuminated probabilistic aspects, with the number of piles equaling the LIS length.[4]
Computing the LIS length is a classic dynamic programming problem solvable in O(n^2) time via a table where each entry tracks the longest increasing subsequence ending at a given position.[5] An optimal O(n \log n)-time algorithm, achieving the information-theoretic lower bound up to lower-order terms, was presented by M. L. Fredman in 1975 using a variant of patience sorting combined with binary search to maintain the smallest possible tail values for each subsequence length.[6] In the context of random permutations of = \{1, 2, \dots, n\}, the expected LIS length grows asymptotically as $2\sqrt{n}, with finer Tracy–Widom fluctuations established through connections to random matrix theory.[4]
Fundamentals
Definition
In the longest increasing subsequence (LIS) problem, given a sequence A = (a_1, a_2, \dots, a_n) of n real numbers, the objective is to identify a subsequence of maximum length in which the elements are strictly increasing.[5] A subsequence is formed by selecting elements while preserving their relative order in the original sequence, specified by strictly increasing indices $1 \leq i_1 < i_2 < \dots < i_k \leq n such that a_{i_1} < a_{i_2} < \dots < a_{i_k}.[5] The problem typically assumes the elements are distinct, but when duplicates are present, equal elements cannot be included in the same strictly increasing subsequence due to the strict inequality requirement.[5]
A common variation is the longest non-decreasing subsequence, where the condition is relaxed to a_{i_1} \leq a_{i_2} \leq \dots \leq a_{i_k}, allowing equal elements to appear consecutively in the subsequence.[7] This version is particularly relevant when handling sequences with repeated values, as it permits multiple instances of the same number as long as the order is non-decreasing.[7]
The standard output of an LIS algorithm is the length k of the longest such subsequence; however, the actual subsequence can be reconstructed by maintaining a predecessor array during the computation, which records the previous index for each position to allow backtracking from the end of the sequence.[5] While the core LIS problem can be solved in polynomial time—specifically, in O(n \log n) time using efficient methods—certain generalizations, such as the longest subsequence avoiding a specified set of patterns (known as the longest X-subsequence for particular X), are NP-hard.[8][8]
Examples
Consider the sequence $10, 9, 2, 5, 3, 7, 101, 18. One longest increasing subsequence is $2, 5, 7, 18, and another is $2, 3, 7, 101; both have length 4.[9]
Sequences containing negative numbers illustrate that increasing order is defined relative to the values, regardless of sign. For the sequence $3, 7, -1, 2, 4, 8, 5, 6, a longest increasing subsequence is -1, 2, 4, 5, 6, with length 5.[10] In the standard formulation, a longest increasing subsequence requires strictly increasing order, so duplicate (equal) elements cannot appear consecutively in the subsequence. A related variant, the longest non-decreasing subsequence, relaxes this to allow equal elements, where each subsequent element is greater than or equal to the previous.[11]
For permutations of \{1, 2, \dots, n\}, the longest increasing subsequence identifies the longest subset of elements in natural order, preserving relative positions. In the permutation $3, 1, 4, 2, 5 for n=5, one longest increasing subsequence is $1, 2, 5, with length 3./18%3A_Young_Tableaux)
To visualize possible subsequences in the initial example, the table below lists the original sequence with positions and highlights two maximal increasing subsequences of length 4; shorter ones exist, but none longer, as no five elements maintain strict increase while preserving order.
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
| Value | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
| One LIS: | | | 2 | 5 | | 7 | | 18 |
| Another: | | | 2 | | 3 | 7 | 101 | |
Algorithms
Dynamic Programming Approach
The dynamic programming approach provides a straightforward method to compute both the length of the longest increasing subsequence (LIS) and the subsequence itself for a given sequence A = [A_1, A_2, \dots, A_n] of n elements. This method defines subproblems based on the longest increasing subsequence ending at each position in the sequence, allowing the solution to be built incrementally from smaller prefixes.[12]
The core of the algorithm is the array L[1..n], where L represents the length of the LIS ending at index i. The recurrence relation is given by:
L =
\begin{cases}
1 + \max\{ L \mid 1 \leq j < i \ \text{and} \ A < A \} & \text{if there exists such a } j, \\
1 & \text{otherwise}.
\end{cases}
All L are initialized to 1, as each single element forms an increasing subsequence of length 1. The overall LIS length is then \max_{1 \leq i \leq n} L. This formulation ensures that optimal substructure holds, as any LIS ending at i extends the longest possible increasing subsequence from earlier positions with smaller values.[12]
The bottom-up computation proceeds in a single pass over the sequence, iterating from left to right. The following pseudocode illustrates the process for computing the lengths:
function LIS_length(A, n):
L = [array](/page/ARRAY) of size n, initialized to 1
for i = 1 to n:
for j = 1 to i-1:
if A[j] < A[i] and L[j] + 1 > L[i]:
L[i] = L[j] + 1
return max(L)
function LIS_length(A, n):
L = [array](/page/ARRAY) of size n, initialized to 1
for i = 1 to n:
for j = 1 to i-1:
if A[j] < A[i] and L[j] + 1 > L[i]:
L[i] = L[j] + 1
return max(L)
This implementation requires O(n^2) time due to the nested loops, each pair examining potential predecessors, and O(n) space for the L array. For large n, the quadratic time complexity becomes a bottleneck, limiting practicality to sequences up to roughly $10^4 elements.[12]
To reconstruct the actual subsequence, maintain a predecessor array P[1..n], where P stores the index j that achieves the maximum in the recurrence for L (or 0 if none). After computing all L, identify the index k = \arg\max_i L, then backtrack from k using P: append A to the result (in reverse), set k = P, and repeat until k = 0. Reverse the collected elements to obtain the LIS. This adds negligible time overhead beyond the initial computation.[12]
The correctness of this approach follows by induction on the sequence length. Base case: For n=1, L{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}=1 trivially holds. Inductive step: Assume the relation computes correct lengths for the prefix up to i-1. For position i, L considers all valid extensions from prior optimal endings with smaller values, selecting the maximum possible length; if no extension is possible, it defaults to 1. Thus, L is optimal for subsequences ending at i, and the global maximum yields the LIS length. The reconstruction faithfully traces this optimal path via predecessors.[12]
Patience Sorting and Binary Search Method
The patience sorting method provides an intuitive way to compute the length of the longest increasing subsequence (LIS) by simulating a card game. In this approach, the input sequence is treated as a deck of cards dealt one by one into piles, where each pile represents the smallest possible tail value for an increasing subsequence of a given length. Specifically, for each element in the sequence, it is placed on the leftmost pile where it can extend the top card (i.e., it is larger than the current top), or it starts a new pile if no such pile exists. The piles are maintained such that the top cards are strictly increasing from left to right. The number of piles at the end equals the length of the LIS, as each pile corresponds to a potential extension of the longest subsequence found so far. This O(n log n)-time algorithm was first presented by M. L. Fredman in 1975.[4][6]
This method can be efficiently implemented using binary search to maintain an array T, where T stores the smallest tail of all increasing subsequences with length i+1. The array T is kept sorted, allowing binary search to locate the correct position for each new element in O(\log n) time. For a strictly increasing subsequence, a lower bound binary search finds the first position in T where the current element can replace a larger tail value without violating the increasing order, or extends the array if it is larger than all existing tails. If the position is beyond the current length of T, the array grows; otherwise, the element replaces the value at that position to keep the potential for longer subsequences minimal.[13]
The algorithm proceeds as follows:
- Initialize an empty array T.
- For each element x in the input sequence A:
- Use binary search to find the smallest index i such that T \geq x (or i equals the current length of T if x is larger than all elements in T).
- If i equals the length of T, append x to T.
- Otherwise, set T = x.
- The length of T is the length of the LIS.
Here is pseudocode for the length computation:
function LIS_length(A):
if A is empty:
return 0
T = [] // empty list
for x in A:
pos = lower_bound(T, x) // first position >= x
if pos == length(T):
append x to T
else:
T[pos] = x
return length(T)
function LIS_length(A):
if A is empty:
return 0
T = [] // empty list
for x in A:
pos = lower_bound(T, x) // first position >= x
if pos == length(T):
append x to T
else:
T[pos] = x
return length(T)
where lower_bound returns the index of the first element in T not less than x, or the length if all are less.[13]
The array T does not represent an actual increasing subsequence but tracks the minimal possible tail values for subsequences of each length, ensuring that the final length of T matches the LIS length. This works because replacing a tail with a smaller value preserves the possibility of extending to longer subsequences later, while the greedy placement minimizes the number of "piles" (or lengths) needed. A proof of correctness relies on showing that no increasing subsequence can exceed the number of piles, and the greedy strategy achieves the minimum number required.[4][13]
The time complexity is O(n \log n), as each of the n elements requires a binary search over at most n positions in T. To reconstruct an actual LIS, the algorithm can be extended by maintaining a predecessor array or indices during updates, tracking which previous element led to each replacement or extension; backtracking from the end then yields one such subsequence in additional O(n) time.[13]
This approach originates from the Robinson–Schensted–Knuth (RSK) correspondence, where the length of the LIS corresponds to the length of the first row in the associated Young tableau built via Schensted insertion, providing a combinatorial foundation for the pile-based intuition.[4]
Online Algorithms
In the online model for the longest increasing subsequence (LIS) problem, elements arrive sequentially in a stream, and the algorithm must process each one immediately upon arrival, making irrevocable decisions without revisiting prior elements or backtracking. This setting is particularly relevant for data streams where storage is limited, and the objective is to output an approximation of the LIS length incrementally after each update, often in a single pass. Unlike offline algorithms that access the full sequence, online methods emphasize constant or sublinear space per element while maintaining computational efficiency.[14]
A straightforward online adaptation of dynamic programming maintains an array tracking the smallest possible tail values for all increasing subsequences of various lengths encountered so far, updating it via binary search for each new element. This approach, akin to the patience sorting method for intuition, processes elements in O(n log n) total time with O(n) space but requires storing potential candidates up to the current LIS length. However, in space-constrained streaming environments, this O(n) space requirement becomes prohibitive for large n, limiting its practicality and motivating approximation techniques.[15]
To address space limitations, approximation algorithms have been developed for the streaming model. A seminal result by Liben-Nowell, Vee, and Zhu showed that any deterministic one-pass streaming algorithm computing the exact LIS length requires Ω(√n) space in the worst case, establishing a fundamental lower bound. Building on this, Gopalan, Jayram, Krauthgamer, and Kumar introduced a deterministic one-pass algorithm that achieves a (1 + ε)-approximation to the LIS length using O((√n log n)/ε) space for any ε > 0, marking a significant advance in balancing accuracy and efficiency. These methods maintain a sampled set of candidate tails or use sketching techniques to estimate subsequence lengths without full storage.
For random inputs, such as uniform random permutations, an optimal online strategy focuses on irrevocable selection decisions to maximize the expected length of the built subsequence. In this decision-theoretic model, a threshold-based approach maintains the last selected element y and accepts a new element x > y if x - y falls below a dynamic threshold ψ depending on the remaining time horizon and current position. Gnedin and Seksenbayev analyzed self-similar threshold strategies, demonstrating that the optimal expected length is asymptotic to √(2n), with the constant √2 arising from renewal theory and diffusion approximations. This performance is achieved by tuning the threshold to balance greediness and future opportunities, yielding a strategy within O(1) of the true optimum.
Competitive analysis reveals stark differences between adversarial and random cases. In the worst-case adversarial streaming model, no constant-factor approximation is possible with o(n) space for exact recovery, but the aforementioned (1 + ε)-approximations provide multiplicative guarantees relative to the offline optimum. For random permutations, where the offline expected LIS length is approximately 2√n, the threshold-based online strategy yields a competitive ratio of about 1/√2 ≈ 0.707, highlighting the inherent information loss from irrevocable decisions. Lower bounds confirm that randomized streaming algorithms require Ω(n) space for exact computation, underscoring the trade-offs in expected performance.[16]
Online LIS algorithms find applications in real-time stream processing, such as detecting increasing patterns in sensor networks for anomaly detection or analyzing rising trends in financial time series like stock prices, where data arrives continuously and decisions must be made on the fly. For instance, in sequential databases, structures like quadruple neighbor lists enable efficient online queries for constrained LIS over streaming sequences.[17]
A key limitation of online algorithms is their inability to guarantee the exact offline LIS length without full sequence access, as irrevocable processing precludes global optimization and space lower bounds prevent exact recovery in sublinear space. Even in the random case, the threshold strategy falls short of the offline expectation by a constant factor, emphasizing the model's constraints for practical deployment.[16]
Theoretical Results
Length Bounds
The Erdős–Szekeres theorem, established in 1935, provides a fundamental worst-case bound on the length of the longest increasing subsequence in any sequence of distinct real numbers. Specifically, any sequence of more than (k-1)(m-1) distinct real numbers contains either an increasing subsequence of length at least k or a decreasing subsequence of length at least m.[18] This result guarantees that sufficiently long sequences must possess a monotone subsequence of notable length, establishing a minimal assurance for the longest increasing subsequence (LIS) in the worst case.
The proof of the theorem relies on the pigeonhole principle applied to auxiliary sequences derived from the original. For a sequence a_1, a_2, \dots, a_n of distinct reals, define for each position i the value u_i as the length of the longest increasing subsequence ending at i, and v_i as the length of the longest decreasing subsequence ending at i. If no increasing subsequence of length k exists, then each u_i \leq k-1; similarly, if no decreasing subsequence of length m exists, then each v_i \leq m-1. The pairs (u_i, v_i) thus take values in a set of size at most (k-1)(m-1). By the pigeonhole principle, if n > (k-1)(m-1), there exist indices i < j with (u_i, v_i) = (u_j, v_j). If a_i < a_j, then appending a_j to the increasing subsequence ending at i yields one of length u_i + 1 > u_j, a contradiction; if a_i > a_j, a similar contradiction arises for the decreasing subsequence. This forces either a long increasing or decreasing subsequence.[18]
An immediate upper bound on the LIS length follows trivially from the definition: in any sequence of n elements, no increasing subsequence can exceed length n, as it cannot reuse elements while preserving order. This contrasts with the Erdős–Szekeres lower bound, which ensures an LIS of length at least roughly \sqrt{n} in sequences of length n (by setting k = m \approx \sqrt{n+1}).[18]
The Erdős–Szekeres bound is tight up to a constant factor, as demonstrated by explicit constructions of sequences where the LIS length is \Theta(\sqrt{n}). One such construction partitions the sequence into \sqrt{n} decreasing subsequences, each of length \sqrt{n}, arranged so that no longer increasing subsequence forms across partitions. By Mirsky's theorem—the dual of Dilworth's theorem—the length of the longest chain (increasing subsequence) in the associated poset equals the minimum number of antichains (decreasing subsequences) needed to cover the sequence. Thus, covering with \sqrt{n} decreasing subsequences implies LIS length at most \sqrt{n}. A concrete realization merges \sqrt{n} decreasing runs of length \sqrt{n} in a grid-like order, yielding a sequence of length n with no increasing subsequence longer than \sqrt{n}.[18][19][20]
These results extend naturally to more general settings. In the context of partial orders, Dilworth's and Mirsky's theorems provide analogous bounds: the height (longest chain) equals the minimum antichain cover, allowing constructions where the longest chain is bounded by partitioning into few antichains. For multisets permitting repeated elements, the theorem adapts to non-decreasing subsequences, but the strict inequality bound requires adjustment, with sequences of repeated values yielding LIS length 1.[20][19]
Probabilistic Analysis
In the random permutation model, where a uniform random permutation of the integers \{1, 2, \dots, n\} is considered, the expected length of the longest increasing subsequence, denoted L_n, satisfies \mathbb{E}[L_n] \sim 2\sqrt{n} as n \to \infty. This asymptotic behavior was first established independently by Vershik and Kerov (1977), and by Logan and Shepp (1977), building on earlier work by Hammersley (1972) that showed the limit exists and is finite.[4] The problem originates from Ulam's conjecture in 1961, which posited that L_n grows on the order of \sqrt{n} based on initial Monte Carlo simulations.
A landmark result is the Baik-Deift-Johansson theorem, which provides the precise limiting distribution of the centered and scaled L_n. Specifically,
\frac{L_n - 2\sqrt{n}}{n^{1/6}} \to \mathcal{F}_2
in distribution as n \to \infty, where \mathcal{F}_2 is the Tracy-Widom distribution for the largest eigenvalue of a Gaussian unitary ensemble in random matrix theory.[21] This theorem connects the combinatorics of permutations to advanced analytic tools, including Riemann-Hilbert problems and Toeplitz determinants. The scaling implies that the variance of L_n is asymptotically c n^{1/3} for some constant c > 0 (with the n^{1/6} factor in the denominator reflecting the standard deviation order), and the distribution exhibits strong concentration around the mean, with high-probability bounds of the form |L_n - 2\sqrt{n}| = O(n^{1/6 + \epsilon}) for any \epsilon > 0 holding with probability approaching 1.[21]
Computational verifications for small n confirm these asymptotics; for instance, exact enumerations and simulations show that \mathbb{E}[L_n]/\sqrt{n} approaches 2 closely even for n up to a few thousand, with fluctuations matching the Tracy-Widom tail behaviors observed in random matrices.
Extensions to other random models preserve the core asymptotic. For non-uniform random permutations, such as those drawn from the Plancherel measure on Young tableaux, the expected L_n remains \sim 2\sqrt{n}, though the limiting distribution may differ.[22] Similarly, for sequences of n i.i.d. continuous random variables (e.g., uniform on [0,1]), the longest strictly increasing subsequence has expected length \sim 2\sqrt{n}, with the same leading-order growth due to the absence of ties and analogous Poisson point process limits.[23]
Connections and Applications
The longest increasing subsequence (LIS) problem is closely connected to partially ordered sets (posets), where the elements of the sequence form a poset under the order defined by both their positions and values: an element precedes another if it appears earlier in the sequence and has a smaller value. In this poset, the length of the LIS corresponds exactly to the size of the longest chain, a totally ordered subset.[24] By Dilworth's theorem, which states that in any finite poset the size of the largest antichain equals the minimum number of chains needed to cover the poset, the LIS length is dual to the size of the longest antichain, often corresponding to the longest decreasing subsequence in permutation contexts.
The LIS problem can be viewed as a special case of the longest common subsequence (LCS) problem. Specifically, for a permutation \sigma of the numbers $1 to n, the LIS of \sigma is equivalent to the LCS between \sigma and the sorted sequence $1, 2, \dots, n. Both problems share similar dynamic programming approaches, with the standard O(n^2) algorithm for LIS mirroring the DP table used for LCS, where entries represent the longest subsequence ending at particular positions.[8]
Patience sorting provides a direct method to compute the LIS length through a simulation of card piles, where each pile represents the smallest possible tail for all increasing subsequences of a given length. The number of piles formed equals the LIS length, and this process links to Young tableaux, as the pile structure underlies the insertion algorithm in the Robinson–Schensted–Knuth (RSK) correspondence.[25]
The Robinson–Schensted correspondence establishes a bijection between permutations of n elements and pairs of standard Young tableaux of the same shape, where the length of the first row in the insertion tableau equals the length of the longest increasing subsequence in the permutation. This connection, originally developed by Robinson in 1938 and extended by Schensted, reveals deep combinatorial structures tying LIS to symmetric group representations and jeu de taquin operations on tableaux.[1]
For broader settings, LIS extends to maximum non-crossing matchings in convex bipartite graphs, where the matching size equates to the LIS length under positional and value constraints, linking to applications in sequence alignment and partial orders.[26]
While the standard LIS problem is solvable in polynomial time via dynamic programming in O(n^2) or O(n \log n) using binary search, certain generalizations are NP-hard. For instance, the longest X-subsequence problem, where X is a class of forbidden permutation patterns, reduces to NP-hard cases beyond the identity pattern of standard LIS. Similarly, weighted variants, such as the longest weighted common increasing subsequence with arbitrary weights, are NP-complete even for small alphabets.[8][27]
Practical Applications
In bioinformatics, the longest increasing subsequence (LIS) algorithm is employed for aligning high-scoring segment pairs generated by tools like BLAST in genome sequencing, where it orders fragments based on their relative positions to improve mapping accuracy when aligning sequences to a reference genome, such as the human genome.[28] This approach facilitates the identification of homologous sequences by finding the longest chain of increasing coordinates, aiding in the assembly of large-scale genomic data.[28]
In finance, LIS is applied to stock price analysis within time-series data streams to identify upward trends, where a longer LIS length indicates a stable increasing pattern despite fluctuations, and the gap between the subsequence's endpoints quantifies growth intensity.[17] For instance, in real-time monitoring, LIS computation over sliding windows of price sequences helps detect potential investment opportunities by highlighting periods of sustained price ascent.[17]
Practical implementations of LIS often leverage efficient libraries; for example, Python's bisect module enables the O(n log n) patience sorting method by maintaining sorted tails during binary searches, suitable for sequences up to n ≈ 10^6 on standard hardware.[29]
Variations in practice include constrained LIS, which incorporates additional restrictions like minimum height or sequence dependencies for resource-limited environments, such as embedded systems processing sequential data under memory constraints.[30] Weakly increasing subsequences extend the standard LIS to allow equal elements, accommodating approximate matches in noisy or real-valued data for applications like partial sequence alignment.[31]