思路 为了让子序列更长，让每一个长度的最长上升子序列的末尾元素尽可能小，这样后面元素能接到这个子序列的可能就更大。 所以，创建一个 dp 向量，用来存储各个长度的子序列末尾的最小元素。 那么考虑 arr 数组下的每一个元素 x ，遍历 dp 向量，如找到 x < dp[i] ，停止遍历： 1. x < dp[i] ：找到了第一个末尾元素大于 x 的子序列长度 i ，前面所有的子序列长度最小末尾元素均小于 x ，所以当前 x可以放在长度为 i-1 的子序列末尾，此时新形成的子序列长度为 i ，末尾元素又小于 dp[i] ，因此这个元素应当取代 dp[i] ； 2. x >= dp[i] ：继续遍历，x 无法加入此前任何一个子序列使得它的末尾元素更小。（如果 dp 数组已经遍历完了，就代表 x 只能放在长度为 dp.size() 的子序列末尾构成长度为 dp.size()+1 的子序列，所以 dp.push_back(x) ） 当 arr 数组遍历完成，dp.size() 即为所求。 当然，因为遍历规则，dp 向量的元素呈非严格递减排列，因此可以使用二分查找优化遍历 dp 向量的过程。 代码 声明：个人学习经验，如有谬误，欢迎指出。

这样看着舒服点 然而还能更简单(bushi 这还不是最简单的 最简单的如下

#include <iostream> #include <cmath> #include <algorithm> using namespace std; int main() { int n; int a[1100], f[1100], ans = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; f[i] = 1; } for (int i = 2; i <= n; i++) for (int j = 1; j < i; j++) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); for (int i = 1; i <= n; i++) ans = max(ans, f[i]); cout << ans; }

这个看着舒服点

#include<bits/stdc++.h> using namespace std; int n,a[200005],dp[200005],big=INT_MIN,x; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=1; } for(int i=1;i<=n;i++){ for (int j = 1; j < i; j++){ if(a[j]<a[i])dp[i] = max(dp[i], dp[j] + 1); big=max(dp[i],big);}} }

#include <bits/stdc++.h> using namespace std; int n; int a[1007]; int dp[1007]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } int ans = 0; for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = 1; j <= i; j++) { if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } cout << ans << endl; }

复制： #include<iostream> using namespace std; int main(){ int dp[1005][2],a[1005],n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ dp[i][1]=1; dp[i][0]=0; for(int j=1;j<=n;j++){ if(a[i]>a[j]) dp[i][1]=max(dp[i][1],dp[j][1]+1); dp[i][0]=max(dp[i][0],max(dp[j][1],dp[j][0])); } } cout<<max(dp[n][0],dp[n][1]); }