算法 · 进阶 · 前置：子序列、LIS 与简单计数 · 约 18 分钟
单调子序列构造：块内下降，块间上升
不只求最长长度，这次反过来造一个排列，让最长单调子序列恰好长 k。
目标 max(LIS, LDS) = 3 · 8 ≤ 3² = 9
横轴：原排列位置；纵轴：数值。虚点为计划，实点为已构造。路径只沿位置向右。
当前前缀：LIS=0 · LDS=0；完成后：LIS=⌈8/3⌉=3，LDS=3
0/3 · 把 1…8 按每块至多 3 个切开，再把每块倒序。先预测块内与块间的走势。
滑块可用方向键及 Home / End。改变输入会重置步骤；n 调小时 k 随之限制到 n。图形范围 1–16，算法代码模型支持到100。减少动画关闭播放，仍可单步。
同一步，对照构造
// 输入：n=8, k=3；1 ≤ k ≤ n ≤ 100
if (n > k * k) return IMPOSSIBLE;
for (low = 1; low <= n; low += k) {
high = min(n, low + k - 1);
for (value = high; value >= low; value--)
output(value);
}
// 已输出 0/8 项：尚未开始
// 构造O(n)；图中证书另用O(n²)动态规划校验图上的递增与递减高亮是当前前缀的真实子序列，不是 tails 表。没有输出完整排列前，不能把前缀的长度误当成最终结果。
先预测：n=5、k=5 时，LIS 也必须等于5吗？
不必。[5,4,3,2,1] 的 LIS=1，LDS=5，max=5，已经满足题意。要求两者都等于5是不同的问题。
看完图，带走这些结论
对于1到n的排列，要求最长单调子序列恰为k，就是max(LIS,LDS)=k，其中LIS严格递增、LDS严格递减。可行当且仅当1≤k≤n≤k²。将连续值按每块k个切分，再把各块倒序，得到LDS=k、LIS=⌈n/k⌉≤k。
适用条件与边界
n、k为正整数，1≤k≤n，元素是1到n各一次，不能重复或遗漏。单调子序列保留原位置顺序，允许跳过元素；不是连续片段，也不要求LIS与LDS分别都等于k。图形范围n≤16，算法模型n≤100；数学结论不限于这个演示上界。
始终保持的规律
已输出的块内部严格下降，后块的所有值大于前块；每个整数1到n恰好输出一次。第一块长度k，总块数不超过k。
逐步例子
- 取n=8、k=3。先按值分块：[1,2,3]、[4,5,6]、[7,8]；各块倒序得到[3,2,1,6,5,4,8,7]。图中横轴是位置，纵轴是数值。
- 块内下降：递增子序列在同一块至多选一个。块间上升：后块的所有值都更大，所以每块选一个便能递增。因此LIS等于块数⌈8/3⌉=3。
- 递减子序列不能跨块，因为后块所有值都更大；最长下降块长度为3，所以LDS=3。两者最大值为3，满足目标。
- 若n=5、k=5，只需一块[5,4,3,2,1]。LIS=1、LDS=5，最大值仍为5；无需让两者都等于5。
- 为什么n>k²不可能？给每个元素标记(I,D)：以它结尾的最长递增和递减子序列长度。对先后两个位置i<j，值不同：若aᵢ<aⱼ，则Iⱼ≥Iᵢ+1；否则Dⱼ≥Dᵢ+1。因此任意两处标签不同。
- 若LIS、LDS都不超过k，所有标签只有k×k种。n个元素需要n种不同标签，所以n≤k²。n=10、k=3需要10个标签，却只有9种，矛盾。
- 反过来，当k≤n≤k²，第一块恰有k个元素，最后一块可不足k；总块数⌈n/k⌉≤k。于是LDS=k、LIS≤k，保证最大值恰为k。
构造、证书与复杂度
每个数恰好输出一次，构造时间O(n)，若保存输出则空间O(n)，流式输出额外空间O(1)。图形为验证当前前缀另用O(n²)动态规划计算两种长度，这不是构造本身的复杂度。大整数实现须避免k*k溢出，可改用⌈n/k⌉≤k的安全比较；本模型n≤100可精确计算。
常见误区
- 把max(LIS,LDS)=k误读成两者都等于k：例如n=k=5的递减排列已满足目标。
- 只限制每块大小，却不限制块数：n=10、k=3会产生4块，每块取一个便有长度4的递增子序列。
- 打乱块的值域顺序：证明需要后一块的每个值都大于前一块；随意分组不能保证。
- 把连续下降块当作子序列定义：递减路径恰好可选完整一块，但一般子序列不要求连续。
- 把n≤k²当充分条件而忘了k≤n：长度不可能超过元素总数。n=1时只有k=1；k=1也只能n=1。
- 把重复值数组直接套入标签证明：不同元素必有一个严格大小关系，排列条件是必要前提。
自测与答案
n=7、k=3能否构造？n=5、k=2呢？n=3、k=3需要LIS也为3吗？
7≤9，构造[3,2,1,6,5,4,7]，LIS=3、LDS=3。5>4，不可行。[3,2,1]已有LIS=1、LDS=3，满足max=3。