什么是最长递减子序列？-野牛程序员
作者：野牛程序员：2025-08-03 17:33:23数据结构阅读 2759
什么是最长递减子序列
最长递减子序列 (Longest Decreasing Subsequence, LDS)
定义
最长递减子序列是指在一个给定的数字序列中，找到一个最长的子序列，使得这个子序列中的元素按照递减的顺序排列。
关键概念解释
子序列：从原序列中删除若干个元素（也可以不删除）后得到的新序列，但保持原有元素的相对顺序
递减：序列中后面的元素严格小于前面的元素
最长：在所有可能的递减子序列中，长度最大的那个
举例说明
假设有一个序列：[9, 5, 5, 5, 4, 2, 1]
递减子序列的例子：
[9, 5]- 长度为2[9, 4, 2, 1]- 长度为4[5, 4, 2, 1]- 长度为4[9, 5, 4, 2, 1]- 长度为5（最长递减子序列）
生活中的类比
想象你在整理书架，书按照高度排列。最长递减子序列就像是你要找出按照高度严格递减排列的最长的一排书的数量。
比如书的高度是：[9cm, 5cm, 5cm, 5cm, 4cm, 2cm, 1cm]
你可以选择的最长递减序列就是：[9cm, 5cm, 4cm, 2cm, 1cm]，共5本书。
与相关概念的区别
最长递增子序列(LIS)：元素按递增顺序排列
最长公共子序列(LCS)：两个序列的公共部分
子数组/子串：必须连续的元素序列，而子序列可以不连续
算法思路
通常使用动态规划来解决：
对于每个位置的元素，计算以该元素结尾的最长递减子序列长度
通过比较前面所有比当前元素大的元素的状态来更新当前状态
最终答案是所有位置中长度的最大值
这就是最长递减子序列的基本概念，它在算法和实际应用中都有重要作用。
最长递减子序列 (LDS) 的 C++ 实现
方法一：动态规划解法（时间复杂度 O(n²)）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算最长递减子序列的长度
int longestDecreasingSubsequence(vector<int>& arr) {
int n = arr.size();
if (n == 0) return 0;
// dp[i] 表示以 arr[i] 结尾的最长递减子序列长度
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// 如果前面的元素大于当前元素，则可以构成递减序列
if (arr[j] > arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// 返回所有位置中最长的递减子序列长度
return *max_element(dp.begin(), dp.end());
}
// 打印最长递减子序列
vector<int> printLDS(vector<int>& arr) {
int n = arr.size();
vector<int> dp(n, 1);
vector<int> parent(n, -1);
// 构建 dp 数组和 parent 数组
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
}
// 找到最长递减子序列的末尾位置
int maxLength = 0;
int lastIndex = 0;
for (int i = 0; i < n; i++) {
if (dp[i] > maxLength) {
maxLength = dp[i];
lastIndex = i;
}
}
// 重构序列
vector<int> lds;
int current = lastIndex;
while (current != -1) {
lds.push_back(arr[current]);
current = parent[current];
}
reverse(lds.begin(), lds.end());
return lds;
}
方法二：优化解法（时间复杂度 O(n log n)）
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 使用二分查找的优化版本
int longestDecreasingSubsequenceOptimized(vector<int>& arr) {
int n = arr.size();
if (n == 0) return 0;
// tails[i] 表示长度为 i+1 的递减子序列的最小尾部元素
vector<int> tails;
for (int i = 0; i < n; i++) {
// 使用二分查找找到第一个小于等于 arr[i] 的位置
auto it = upper_bound(tails.begin(), tails.end(), arr[i], greater<int>());
if (it == tails.end()) {
// 如果没找到，说明 arr[i] 可以构成更长的递减子序列
tails.push_back(arr[i]);
} else {
// 否则替换找到位置的元素
*it = arr[i];
}
}
return tails.size();
}
完整示例程序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestDecreasingSubsequence(vector<int>& arr) {
int n = arr.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
vector<int> printLDS(vector<int>& arr) {
int n = arr.size();
vector<int> dp(n, 1);
vector<int> parent(n, -1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
}
int maxLength = 0;
int lastIndex = 0;
for (int i = 0; i < n; i++) {
if (dp[i] > maxLength) {
maxLength = dp[i];
lastIndex = i;
}
}
vector<int> lds;
int current = lastIndex;
while (current != -1) {
lds.push_back(arr[current]);
current = parent[current];
}
reverse(lds.begin(), lds.end());
return lds;
}
int main() {
vector<int> arr = {9, 5, 5, 5, 4, 2, 1};
cout << "数组: ";
for (int x : arr) cout << x << " ";
cout << endl;
int length = longestDecreasingSubsequence(arr);
cout << "最长递减子序列长度: " << length << endl;
vector<int> lds = printLDS(arr);
cout << "最长递减子序列: ";
for (int x : lds) cout << x << " ";
cout << endl;
return 0;
}
算法说明
基础动态规划方法：
时间复杂度：O(n²)
空间复杂度：O(n)
适用于小规模数据
优化二分查找方法：
时间复杂度：O(n log n)
空间复杂度：O(n)
适用于大规模数据
两种方法都能有效解决最长递减子序列问题，可以根据具体需求选择合适的实现。
如何理解最长递减子序列
🎯 生活化的故事
故事场景：下楼梯游戏
想象你在一个大楼里，每层楼都有一个数字标牌：
楼层: 1 2 3 4 5 6 7
数字: [9, 5, 5, 5, 4, 2, 1]
规则：你只能向下走，而且每次走到的楼层数字必须比当前楼层小
目标：找到能走的最多步数
🎲 互动游戏
游戏1：找数字路径
给出数字序列：[9, 5, 5, 5, 4, 2, 1]
用手指按规则"走"：
✓ 9 → 5 → 4 → 2 → 1 （5步）
✓ 9 → 5 → 2 → 1 （4步）
✗ 9 → 5 → 5 （错误！没有变小）
问：哪条路能走最多步？
答：第一条路最棒！走了5个数字
🎨 图形化展示
画图法：
把数字画成楼梯：
9
\
5 5 5
\ | /
\ | /
4
\
2
\
1
最长的下降路径：9→5→4→2→1 （共5个数字）
🧠 简单步骤教学
三步理解法：
找 - 找一个开始的数字（通常选最大的）
跳 - 跳到比它小的数字上（必须严格变小）
数 - 数一数最多能跳几步
口诀记忆：
大到小，往下跳，
选最多，要记牢！
不连续，也可以，
顺序对，就最好！
🎮 实际操作
练习题1：
数字序列：[10, 3, 8, 2, 7, 1]
让孩子用不同颜色的笔画出可能的路径：
- 路径1：10→3→2→1 （4步）
- 路径2：10→8→7→1 （4步）
- 路径3：10→8→2→1 （4步）
最长路径长度：4
练习题2（更简单）：
数字序列：[5, 4, 3, 2, 1]
只有一条路：5→4→3→2→1 （5步）
🏆 小测验示例
挑战题：[8, 3, 6, 2, 5, 1]
看谁能找到最长的下降路径？
正确答案：8→6→5→1 或 8→6→2→1 （都是4步）
野牛程序员教少儿编程与信息学奥赛-微信|电话：15892516892
