題意
給定長度為n的序列，求最長上升子序列
復(fù)雜度
O(nlogn)
題解
網(wǎng)上有很多關(guān)于最長上升子序列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;
}
