posts - 217, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Longest Increasing Subsequence

Posted on 2007-07-31 22:30 魔のkyo 阅读(471) 评论(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;
}
只有注册用户登录后才能发表评论。