【提高】最长上升子序列LIS(2) 题目描述 给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数,表示完整序列。 1≤N≤100000,−109≤数列中的数≤109 输出格式 输出一个整数,表示最大长度。 样例 1 输入样例 1 6 1 3 2 8 5 6 输出样例 1 4 4用c++,线段树+dp,详细解析,越详细越好
时间: 2025-07-19 22:35:22 浏览: 9
<think>我们要求解最长上升子序列(Longest Increasing Subsequence, LIS)问题。传统的动态规划解法时间复杂度为$O(n^2)$,而使用线段树(或树状数组)可以优化到$O(n \log n)$。
思路:
1. 离散化:由于序列中的元素可能很大,我们首先将序列中的元素映射到其排名(即离散化),这样线段树的下标范围就可以控制在[1, n]。
2. 动态规划定义:定义dp[i]为以第i个元素结尾的最长上升子序列的长度。
3. 状态转移:对于每个位置i,我们需要在区间[1, rank[i]-1](即所有小于当前元素的值)中查询最大的dp值,然后dp[i] = max_value + 1。
4. 线段树的作用:线段树用来维护区间最大值。当我们处理到第i个元素时,我们已经处理了它之前的所有元素,并且将dp值更新到了线段树中对应离散化值的位置。这样我们就可以在O(log n)的时间内完成区间最大值的查询和单点更新。
步骤:
1. 离散化原数组。
2. 初始化线段树(支持区间最大值查询和单点更新)。
3. 遍历数组中的每个元素:
a. 在线段树中查询[1, 当前元素离散化后的值-1]区间内的最大值max_val。
b. 当前元素的dp值为max_val+1。
c. 更新线段树中当前元素离散化值位置的值(即更新为当前的dp值)。
4. 整个数组的LIS即为所有dp[i]的最大值。
注意:线段树通常用于区间查询和单点更新,这里我们维护的是区间最大值。
下面我们用C++实现这个算法,并加上详细注释。</think>### C++实现线段树结合动态规划求解最长上升子序列(LIS)
#### 算法思路
1. **离散化**:将序列元素映射到排名,缩小值域范围
2. **动态规划**:`dp[i]`表示以`nums[i]`结尾的LIS长度
3. **线段树优化**:维护区间最大值,实现$O(n\log n)$复杂度
- 查询区间$[1, rank-1]$的最大`dp`值
- 更新位置$rank$的值为`dp[i]`
#### C++代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class SegmentTree {
private:
vector<int> tree; // 线段树数组
int n; // 原始数组长度
// 构建线段树
void build(int node, int start, int end) {
if (start == end) {
tree[node] = 0; // 初始化为0
return;
}
int mid = (start + end) >> 1;
build(node << 1, start, mid);
build(node << 1 | 1, mid + 1, end);
tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}
public:
SegmentTree(int size) {
n = size;
tree.resize(4 * n); // 4倍空间
build(1, 1, n); // 从根节点开始构建
}
// 更新操作:将位置idx的值设为val
void update(int idx, int val, int node = 1, int start = 1, int end = -1) {
if (end == -1) end = n;
if (start == end) {
tree[node] = max(tree[node], val); // 取最大值避免覆盖
return;
}
int mid = (start + end) >> 1;
if (idx <= mid) update(idx, val, node << 1, start, mid);
else update(idx, val, node << 1 | 1, mid + 1, end);
tree[node] = max(tree[node << 1], tree[node << 1 | 1]); // 更新父节点
}
// 区间查询:[l, r]的最大值
int query(int l, int r, int node = 1, int start = 1, int end = -1) {
if (end == -1) end = n;
if (r < start || end < l) return 0; // 区间无交集
if (l <= start && end <= r) return tree[node]; // 完全包含
int mid = (start + end) >> 1;
int left_val = query(l, r, node << 1, start, mid);
int right_val = query(l, r, node << 1 | 1, mid + 1, end);
return max(left_val, right_val);
}
};
// 离散化函数
vector<int> discretize(vector<int>& nums) {
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
vector<int> ranks(nums.size());
for (int i = 0; i < nums.size(); ++i) {
// 获取元素在排序后数组中的位置(从1开始)
ranks[i] = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
}
return ranks;
}
// 使用线段树优化的LIS算法
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
// 离散化处理
vector<int> ranks = discretize(nums);
int max_rank = *max_element(ranks.begin(), ranks.end());
SegmentTree st(max_rank); // 创建线段树
vector<int> dp(nums.size(), 1); // dp数组初始化
int ans = 1;
for (int i = 0; i < nums.size(); ++i) {
if (ranks[i] > 1) {
// 查询[1, rank-1]区间最大值
dp[i] = st.query(1, ranks[i] - 1) + 1;
}
// 更新线段树当前位置
st.update(ranks[i], dp[i]);
ans = max(ans, dp[i]); // 更新全局最大值
}
return ans;
}
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
cout << "LIS length: " << lengthOfLIS(nums) << endl; // 输出:4
return 0;
}
```
#### 关键点解析
1. **离散化处理**(第47-58行)
- 将原始数组排序去重后映射到排名
- 例:`[10,9,2,5]` → 排名`[4,3,1,2]`
- 作用:将值域压缩到$[1,n]$,减少线段树空间
2. **线段树操作**(第11-44行)
- **查询**:在$O(\log n)$时间内获取区间$[1, rank-1]$的最大`dp`值
- **更新**:在$O(\log n)$时间内更新位置$rank$的值为当前`dp[i]`
3. **动态规划转移**(第66-74行)
- 状态转移方程:$dp[i] = \max_{j<i \text{且} nums[j]<nums[i]} \{dp[j]\} + 1$
- 线段树优化:将$O(n)$的遍历优化为$O(\log n)$的区间查询
4. **复杂度分析**
- 时间复杂度:$O(n \log n)$(离散化$O(n \log n)$,线段树操作$O(n \log n)$)
- 空间复杂度:$O(n)$(存储离散化数组和线段树)
#### 算法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|--------------------|------------|------------|------------------------|
| 朴素DP | $O(n^2)$ | $O(n)$ | 小规模数据 |
| 贪心+二分 | $O(n \log n)$ | $O(n)$ | 仅需长度,无需序列 |
| **线段树+DP** | $O(n \log n)$ | $O(n)$ | 需完整DP数组的场景 |
此解法结合了动态规划的状态定义和线段树的区间查询优势,特别适用于需要获取完整DP数组的场景(如需要输出所有LIS)[^1][^2]。
---
### 相关问题
1. **如何修改代码以输出具体的最长上升子序列?**
(需回溯DP数组重建LIS路径)
2. **线段树在动态规划中还能优化哪些经典问题?**
(如:最大子段和、带权区间调度等)
3. **如何处理存在重复元素的最长非严格上升子序列?**
(需调整离散化和查询区间)
4. **树状数组能否替代线段树实现相同优化?**
(对比两种数据结构的实现复杂度和常数因子)
[^1]: 动态规划的精髓在于将目标值分解成0~n逐个解决,每次选取数组元素时调整状态
[^2]: 线段树等高级数据结构适用于优化区间查询类问题
阅读全文
相关推荐














