Loading... # 题目描述 给定一个长度为$N$的数列，求数值严格单调递增的子序列的长度最长是多少。 # 输入 第一行包含整数 $N$。 第二行包含$N$个整数，表示完整序列。 # 输出 输出一个整数， 表示最大的长度 # 数据范围 $1\leq N \leq 100000$ $-10^{9}\leq 数列中的数 \leq 10^{9}$ # 解题思路 通过题目中的数据范围不难发现， 使用传统的最长上升子序列问题的dp方法会因为数据量过大超时， 因此考虑对传统dp进行优化： - 传统的dp方式中， 对于`a[i]`需要和所有的`j<i`的`a[j]`比较， 因此比较费时 - 但实际上如果`j < i && k < i && dp[j]==dp[k]`的情况下， 只需要和`a[j], a[k]`中较小的比较就可以了（贪心思想， 大的成立小的一定成立） - 因此可以维护一个单调递增的序列`q`， 每次遍历到`a[i]`的时候寻找序列`q`中最后一个小于`a[i]`的`a[j]`， 将`a[j+1]`更新为`a[i]` # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; int n; int a[N]; int q[N]; int len = 0; int ans = 0; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) { int l = 0, r = len; while(l < r) { int mid = l + r + 1 >> 1; if(q[mid] >= a[i]) r = mid - 1; else l = mid; } len = max(len, r + 1); ans = max(len, ans); q[l + 1] = a[i]; } cout << ans << endl; return 0; } ``` 最后修改：2025 年 01 月 15 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏