Loading... # 最长上升子序列 ## 朴素版n^2^ ~~~C++ #include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N], f[N]; int main(){ int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++){ f[i] = 1; for(int j = 1; j < i; j ++) if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1); } int ans = 0; for(int i = 1; i <= n; i ++) ans = max(ans, f[i]); cout << ans; return 0; } ~~~ ## 优化版nlogn ~~~C++ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N]; int main(){ int n; cin >> n; vector<int> arr; for(int i = 1; i <= n; i ++) cin >> a[i]; arr.push_back(a[1]); for(int i = 2; i <= n; i ++){ if(a[i] > arr.back()) arr.push_back(a[i]); else *lower_bound(arr.begin(), arr.end(), a[i]) = a[i]; } cout << arr.size(); return 0; } ~~~ 最后修改:2023 年 01 月 10 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 2 如果觉得我的文章对你有用,请随意赞赏