最长不下降子序列

_shining · 2024-04-24 16:47:17 · 算法·理论

时间复杂度：O(nlogn)

#include <iostream>//cin cout
#include <algorithm>//upper_bound 
#include <cstring>//memset
using namespace std;//命名空间
int a[5005], dp[5005];
int main()//主函数
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
memset(dp, 0x3f3f3f3f, sizeof(dp));
int maxn = dp[1];
for(int i = 1; i <= n; i++){
a[i] = *upper_bound(dp + 1, dp + n + 1, a[i]);  
}
int ans = 0;
while(dp[ans + 1] != maxn) ans++;
cout << ans;
return 0;//华丽结束
}