 Increasing subsequence

An increasing subsequence of a finite sequence $x=(x_1,\dots ,x_n)$ in a totally ordered set selects indices $1\le i_1<\cdots <i_m\le n$ such thatHere “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of ^[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 exampleThe 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.