Subsequences

In mathematics, a subsequence of a sequence (a1, a2, a3, ...) is obtained by deleting elements while preserving the original order. If the original sequence is finite, say a1, ..., an, then a subsequence has the form (a_{i1}, a_{i2}, ..., a_{ik}) with 1 ≤ i1 < i2 < ... < ik ≤ n. For an infinite sequence, a subsequence is defined similarly by selecting an increasing sequence of indices.

A subsequence differs from a contiguous subsequence, often called a substring or subarray in computer science, where the remaining elements must be consecutive. For example, from (1, 3, 2, 4, 5) you can take (1, 2, 4, 5) by indices 1, 3, 4, 5 or (3, 4) by 2, 4.

In combinatorics and algorithms, subsequences are central. The longest common subsequence problem asks for the longest subsequence common to two sequences, and it is typically solved by dynamic programming in time proportional to the product of the sequence lengths, O(nm). The Erdős–Szekeres theorem states that every sequence of length ab+1 contains either an increasing subsequence of length a+1 or a decreasing subsequence of length b+1.

In analysis and topology, subsequences are used to study convergence. A subsequence x_{n_k} of a sequence (x_n) converges to x if x_{n_k} → x. The Bolzano–Weierstrass theorem asserts that every bounded sequence in R^n has a convergent subsequence. Subsequence concepts thus connect areas from pure analysis to combinatorial algorithms.