# 单调子序列构造图解：块内下降，块间上升

把连续值分成下降块，用排列散点和真实路径构造max(LIS,LDS)=k；以不同的长度标签解释n≤k²为何必要。

原文 / Canonical: https://crazycloud.cc/learn/monotone-subsequences
作者: crazycloudcc
首次发布: 2026-10-20
更新: 2026-10-20

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

对于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。

## 逐步例子

1. 取n=8、k=3。先按值分块：[1,2,3]、[4,5,6]、[7,8]；各块倒序得到[3,2,1,6,5,4,8,7]。图中横轴是位置，纵轴是数值。
2. 块内下降：递增子序列在同一块至多选一个。块间上升：后块的所有值都更大，所以每块选一个便能递增。因此LIS等于块数⌈8/3⌉=3。
3. 递减子序列不能跨块，因为后块所有值都更大；最长下降块长度为3，所以LDS=3。两者最大值为3，满足目标。
4. 若n=5、k=5，只需一块[5,4,3,2,1]。LIS=1、LDS=5，最大值仍为5；无需让两者都等于5。
5. 为什么n>k²不可能？给每个元素标记(I,D)：以它结尾的最长递增和递减子序列长度。对先后两个位置i<j，值不同：若aᵢ<aⱼ，则Iⱼ≥Iᵢ+1；否则Dⱼ≥Dᵢ+1。因此任意两处标签不同。
6. 若LIS、LDS都不超过k，所有标签只有k×k种。n个元素需要n种不同标签，所以n≤k²。n=10、k=3需要10个标签，却只有9种，矛盾。
7. 反过来，当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。

## 延伸学习

LIS课从已有序列求最长长度；本课反过来构造排列，并同时约束递增与递减长度。

[前置：LIS与真实子序列](https://crazycloud.cc/learn/longest-increasing-subsequence)

## 参考资料

- [CSES 2215：Monotone Subsequences（常青构造题，题页未注明发布日期）](https://cses.fi/problemset/task/2215)
- [CSES 1145：Increasing Subsequence（保持顺序的严格递增子序列）](https://cses.fi/problemset/task/1145)

[返回图解实验室](https://crazycloud.cc/learn)