假设我们求出所有长度为 $m$ 的子序列的 LIS 最小和最大值，则在最小值和最大值之间每个值都可以取到。这是因为我们可以从 LIS 最小的子序列变到 LIS 最大的子序列，每次替换一个数，则这个变化过程中 LIS 每次至多变化 $\pm 1$，因此所有中间值都可以取到。

上述变化过程可以通过二分优化，时间复杂度 $O(n\log^2n)$。

求 LIS 最大值是简单的，只需尽量选原序列的 LIS，然后不够的用其他数补充。

求 LIS 最小值，可以转化成选尽量少的不相交的下降子序列，其长度和等于 $m$。众所周知，选 $k$ 个子序列的答案等于杨表的前 $k$ 行长度之和，但是杨表的前 $k$ 行并不就是我们想要的子序列。这里构造方式需要参照上述结论的证明，即 RSK 算法。杨表的构造过程相当于对排列进行若干次相邻项的交换，保证每次交换都不改变答案，而最终的排列，即杨表的答案是平凡的。因此只需要反向模拟这一交换过程即可还原出所需的子序列。例如，对于连续的三个数 $a,b,c$，如果 $c< a< b$，则可以交换 $b,c$ 而不改变答案。构造方式是：如果 $b,c$ 属于同一个子序列，则把 $c$ 及其所在子序列后面的部分和 $a$ 所在子序列后面的部分交换。

上述交换过程的复杂度是 $O(n^2)$，因此总复杂度是 $O(n^2)$。