题意
给定长度为n的序列，求最长上升子序列
复杂度
O(nlogn)
题解
网上有很多关于最长上升子序列nlogn的求法，我这里不在过多叙述。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[5001],last[5001],ans;
int main()
{
memset(last,127,sizeof(last));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
last[0]=0;
for(int i=1;i<=n;i++)
{
int tmp=lower_bound(last,last+n,a[i])-last;
last[tmp]=min(last[tmp],a[i]);
ans=max(ans,tmp);
}
printf("%d",ans);
return 0;
}
网友评论