最优算法：时间复杂度最坏为nlogn
#include<iostream>
#include<algorithm>
using namespace std;
int f[100000],top;
int main()
{
int n,*p,x;
cin>>n;
top=0;
while (n--)
{
cin>>x;
p=lower_bound(f,f+top,x,greater<int>());
//删掉greater<int>()或换成less<int>()则为最长上升子序列
*p=x;
if (p-f>=top) top++;
}
cout<<top<<endl;
system("pause");
return 0;
}
使用向量动态开辟空间：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v;
vector<int>::iterator it;
int n,x,top;
cin>>n;
while (n--)
{
cin>>x;
it=lower_bound(v.begin(),v.end(),x);
if (it==v.end()) v.push_back(x);
else *it=x;
}
cout<<v.size()<<endl;
system("pause");
return 0;
}
posted on 2011-10-30 17:21
龙在江湖 阅读(276)
评论(0) 编辑 收藏 引用 所属分类:
算法