Posted on 2007-07-31 22:30
魔のkyo 阅读(534)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm
//longest increasing subsequence
//T(n)=O(nlogn)
//在[b,e),之间返回一个指针p,使得*(p-1) <=x && x<*p,特别德,当x<*b时返回b
int* binary(int* b,int* e,int x)
{
int *mid;
if(x<*b)return b;
while(b<e-2){
mid=b+(e-b)/2;
if(*mid<=x)
b=mid;
else
e=mid+1;
}
return e-1;
}
int LIS(int a[],int n)
{
int i,k;
int *b=new int[n];
b[0]=a[0];
k=1;
for(i=1;i<n;++i){
if(b[k-1]<a[i])//此处修改严格或非严格
b[k++]=a[i];
else
*binary(b,b+k,a[i])=a[i];
}
delete [] b;
return k;
}