= Minimum-tail table for increasing subsequences
{title2=$T_\ell$}
For a processed prefix $(x_1,\ldots,x_i)$, the <minimum-tail table for increasing subsequences> stores
$$
T_\ell=\min\{x_{j_\ell}:1\leq j_1<\cdots<j_\ell\leq i,\ x_{j_1}\leq\cdots\leq x_{j_\ell}\},\qquad 1\leq\ell\leq L(x_1,\ldots,x_i).
$$
There is no slot for an unattainable length. The table records <minimum> endings, rather than the terms of one <longest increasing subsequence>. Replacing the value comparisons by $<$ gives the corresponding table for <strictly increasing subsequences>, whose entries are strictly increasing.
Back to article page
