posts - 71,  comments - 41,  trackbacks - 0
计算最长递增子序列的长度
template < class  T >
int  GetLISLen(T  * arr,  int  n)
 {
     if  (n  <   1 )
         return   0 ;

     int  iCurrMaxLen  =   0 ;
     int  left, right, mid;
     int   * last  =   new   int [n]();
    
    last[ 0 ]  =  arr[ 0 ];
    
     for  ( int  i  =   1 ; i  <  n; i ++ )
     {
         if  (arr[i]  >=  last[iCurrMaxLen])
            last[ ++ iCurrMaxLen]  =  arr[i];
         else   if  (arr[i]  <  last[ 0 ])
            last[ 0 ]  =  arr[i];
         else
         {
            left  =   0 ;
            right  =  iCurrMaxLen;

             while  (left  !=  right  -   1 )
             {
                mid  =  (left  +  right)  /   2 ;
                (last[mid]  <=  arr[i])  ?  (left  =  mid) : (right  =  mid);
            }

            last[right]  =  arr[i];
        } // if
        
    } // for

     for  ( int  i  =   0 ; i  <  iCurrMaxLen  +   1 ; i ++ )
     {
        printf( " %d " , last[i]);
         if  (i  !=  iCurrMaxLen)
            printf( " \x20 " );
         else
            printf( " \n " );
    }

     if  (last)
     {
        delete [] last;
        last  =   0 ;
    }

     return  iCurrMaxLen  +   1 ;
}
posted on 2006-11-22 17:45 Charles 阅读(539) 评论(0)  编辑 收藏 引用 所属分类: 面试小算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 Charles Powered By: 博客园 模板提供：沪江博客
<2006年11月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

决定开始写工作日记，记录一下自己的轨迹...

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 48113
  • 排名 - 455

最新评论

阅读排行榜

评论排行榜