PKU POJ 3903 Stock Exchange 最长递增子序列

纸水仙

　　必须要nlogn算法才能过


View Code


#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int L,a[100005];
int list[100005],numoflist;
int bsearch(int value)
{
int l=0,r=numoflist-1,mid;
while (l<r)
{
mid=(l+r)>>1;
if (list[mid]>=value)
r=mid;
else
l=mid+1;
}
return l;
}
int LIS()
{
list[0]=a[0];
numoflist=1;
for (int i=1;i<L;++i)
{
if(a>list[numoflist-1])
list[numoflist++]=a;
else
{
int pos=bsearch(a);
list[pos]=a;
}
}
return numoflist;
}
int main()
{
while(scanf("%d",&L)!=EOF)
{
for (int i=0;i<L;++i)
scanf("%d",&a);
printf("%d\n",LIS());
}
return 0;
}