posts - 71,  comments - 41,  trackbacks - 0
注意,不一定连续递增
template < class  T >  
int  FindLIS(T  * arr,  int  len, T  *&
result)
{
    
int   * last  =   new   int
[len]();
    
int   * track  =   new   int
[len]();
    
int
 left, right, mid;
    
int  iCurrMaxLen  =   0
;

    
if  (len  <   1
)
    
{
        result 
=   0
;
        
return   0
;
    }


    result 
=   0 ;
    last[
0 =   0
;

    
for  ( int  i  =   1 ; i  <  len; i ++

    
{
        
if  (arr[last[iCurrMaxLen]]  <
 arr[i])
        
{
            track[i] 
=
 last[iCurrMaxLen];
            last[
++ iCurrMaxLen]  =
 i;
            
continue
;
        }


        left 
=   0 ;
        right 
=
 iCurrMaxLen;
        
while  (left  <
 right)
        
{
            mid 
=  (left  +  right)  /   2
;

            arr[last[mid]] 
<  arr[i]  ?  left  =  mid  +   1  : right  =
 mid;
        }


        
if  ( /* left <= right &&  */ arr[i]  <  arr[last[left]]) 
        
{
            
if  (left  >   0

                track[i] 
=  last[left  -   1
];
            last[left] 
=
 i;
        }


    }
// for

    
for  (left  =  iCurrMaxLen, right  =  last[iCurrMaxLen]; left  >=   0 ; left -- , right  =  track[right])
        last[left] 
=
 arr[right];

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


    result 
=  last;
    last 
=   0
;

    
return  iCurrMaxLen  +   1
;
}
稍微解释一下,last中存的是所有i长度子序列中last[i]最小的那个值。而track中记录它的前一个值。这样可以沿着track找回去。
posted on 2006-11-22 17:50 Charles 阅读(1410) 评论(2)  编辑 收藏 引用 所属分类: 面试小算法

FeedBack:
# re: 寻找最长递增子序列
2006-11-28 11:58 | 踏雪赤兔
写得有点复杂,可以用STL简化代码。不过看得出,还是O(NlogN)的算法  回复  更多评论
  
# re: 寻找最长递增子序列
2006-11-28 16:18 | Charles
呵呵,因为这是准备面试用的,所以不能写成STL版的  回复  更多评论
  

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


<2006年11月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

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

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 47990
  • 排名 - 455

最新评论

阅读排行榜

评论排行榜