= Increasing subsequence
An <increasing subsequence> of a finite <sequence> $x=(x_1,\ldots,x_n)$ in a <totally ordered set> selects indices $1\leq i_1<\cdots<i_m\leq n$ such that
$$
x_{i_1}\leq x_{i_2}\leq\cdots\leq x_{i_m}.
$$
Here “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of https://cs.carleton.edu/faculty/dlibenno/papers/lis-lcs/lislcs.pdf[Liben-Nowell, Vee and Zhu, Finding Longest Increasing and Common Subsequences in Streaming Data, section 1]{ref}. A <strictly increasing subsequence> instead requires $x_{i_1}<\cdots<x_{i_m}$. Always check which convention an <algorithm> uses, especially when values repeat.
An <increasing subsequence> may skip positions; it neither rearranges values nor requires consecutive positions. Consider the deliberately constructed example
$$
x=(4,1,3,2,2,5,0).
$$
The indices $(2,4,5,6)$ select $(1,2,2,5)$, an <increasing subsequence> of length four. The indices $(2,3,6)$ select $(1,3,5)$, a <strictly increasing subsequence> of length three. In contrast, $(0,1,2,2,3,4,5)$ rearranges the input and is not a <subsequence>. The longest consecutive nondecreasing block is $(2,2,5)$, of length three; requiring consecutive positions would therefore solve a different problem.
Think of an <increasing subsequence> as preserving ordered observations while skipping interruptions. For the example, discarding $4,3,0$ leaves four observations with no downward step. The <longest increasing subsequence> asks how much of the original order can be kept. This is an order comparison, rather than a claim about the size of upward or downward changes: replacing all values by their squares when the values are nonnegative leaves every allowed selection unchanged. More generally, any strictly order-preserving relabeling has this property.
Back to article page
