题目描述
样例
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],q[N];//q[i]存放子序列长度为i的最后一位值,其越小越好,碰到i长度比他最后一位值能更小就更新
int main()
{
int len=0;
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
q[0]=-2e9;
for(int i=0;i<n;i++)
{
if(a[i]>q[len]) q[++len]=a[i];
else
{
int t=lower_bound(q,q+len,a[i])-q;
q[t]=a[i];
}
}
cout<<len<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla