一、算法概述
最长递增子序列（Longest Increasing Subsequence, LIS）是指在一个序列中，找到一个最长的子序列，使得子序列中的元素严格递增。子序列不要求连续，但要求保持原序列中的相对顺序。
例如：
- 序列
[10, 9, 2, 5, 3, 7, 101, 18]的 LIS 是[2, 3, 7, 101]或[2, 5, 7, 101]，长度为 4。 - 序列
[0, 1, 0, 3, 2, 3]的 LIS 是[0, 1, 2, 3]，长度为 4。
LIS 是动态规划的经典问题，有 O(n²) 的 DP 解法和 O(n log n) 的贪心+二分解法。
二、核心思想
方法一：动态规划 O(n²)
定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
状态转移： 对于每个 i，向前扫描 j ∈ [0, i-1]：
- 若
nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)
初始 dp[i] = 1（每个元素自身构成长度为 1 的子序列）。最终答案为 max(dp[i])。
方法二：贪心 + 二分查找 O(n log n)
维护一个数组 tails，tails[k] 表示长度为 k+1 的递增子序列的最小可能末尾元素。
核心思想： 对于每个元素 x：
- 若
x大于tails中所有元素，则x可以扩展当前最长递增子序列，将x追加到tails末尾。 - 否则，在
tails中找到第一个≥ x的元素并替换为x（这不会改变当前 LIS 长度，但为后续更小的元素创造了机会）。
tails 的长度即为 LIS 长度。
三、算法步骤 / 伪代码
O(n²) DP 解法：
dp[0..n-1] = 1
for i = 0 to n-1:
for j = 0 to i-1:
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
O(n log n) 贪心+二分：
tails = []
for each x in nums:
if tails 为空 或 x > tails.back():
tails.push_back(x)
else:
在 tails 中二分查找第一个 ≥ x 的位置 pos
tails[pos] = x
return tails.size()
四、C++ 代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// ==================== O(n²) DP 解法 ====================
int lengthOfLIS_n2(const vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i] = 以 nums[i] 结尾的 LIS 长度
int maxLen = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
cout << "DP 数组: ";
for (int v : dp) cout << v << " ";
cout << endl;
return maxLen;
}
// ==================== O(n log n) 贪心 + 二分 ====================
int lengthOfLIS_nlogn(const vector<int>& nums) {
vector<int> tails; // tails[k] = 长度为 k+1 的 IS 的最小末尾
for (int x : nums) {
// 在 tails 中找第一个 >= x 的位置
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
// x 比所有 tails 中的元素都大，扩展 LIS
tails.push_back(x);
} else {
// 替换第一个 >= x 的元素
*it = x;
}
// 调试输出 tails 的变化过程
cout << "处理 " << x << " 后 tails: ";
for (int v : tails) cout << v << " ";
cout << endl;
}
return tails.size();
}
int main() {
cout << "请输入数组元素个数: ";
int n;
cin >> n;
vector<int> nums(n);
cout << "请输入 " << n << " 个整数: ";
for (int i = 0; i < n; i++) cin >> nums[i];
cout << "\n===== O(n²) DP 解法 =====" << endl;
int lis1 = lengthOfLIS_n2(nums);
cout << "LIS 长度 (DP): " << lis1 << endl;
cout << "\n===== O(n log n) 贪心+二分 =====" << endl;
int lis2 = lengthOfLIS_nlogn(nums);
cout << "LIS 长度 (贪心+二分): " << lis2 << endl;
return 0;
}
五、复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 动态规划 | O(n²) | O(n) | 两重循环，简单直观 |
| 贪心 + 二分 | O(n log n) | 每个元素二分一次，tails 数组 |
注意： 贪心+二分法只能求出 LIS 的长度，不能直接输出 LIS 的具体序列。若需要输出具体序列，可用 O(n²) DP + 回溯，或在贪心法中维护额外的"前驱"信息。
六、应用场景
- 最长递增子序列问题本身： 直接求序列中最长递增部分
- 信封嵌套问题： 按宽度排序后对高度求 LIS（LeetCode 354 俄罗斯套娃信封）
- 任务调度 / 活动安排： 选择最多不冲突的任务
- 求最长不降子序列： 将
lower_bound改为upper_bound - 数组最少递减子序列划分数： Dilworth 定理相关
- 建桥问题 / 布线问题： 实际为二维 LIS
七、经典例题
LeetCode 300. 最长递增子序列
题目描述：
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
O(n log n) 解法代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end())
tails.push_back(x);
else
*it = x;
}
return tails.size();
}
};
扩展：LeetCode 354. 俄罗斯套娃信封问题
题目描述：
给定一些信封的宽度和高度 (w, h)，当另一个信封的宽度和高度都大于这个信封时，这个信封可以放进另一个信封里（类似俄罗斯套娃）。求最多能嵌套多少层。
思路： 按宽度升序排序（宽度相同时高度降序），然后对高度求 LIS（O(n log n)）。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
// 宽度升序，宽度相同时高度降序（确保同宽信封不能嵌套）
sort(envelopes.begin(), envelopes.end(),
[](auto& a, auto& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
vector<int> tails;
for (auto& e : envelopes) {
int h = e[1];
auto it = lower_bound(tails.begin(), tails.end(), h);
if (it == tails.end())
tails.push_back(h);
else
*it = h;
}
return tails.size();
}
};
