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 阅读(1464) 评论(2) 编辑收藏引用所属分类: 面试小算法

FeedBack:

# re: 寻找最长递增子序列

2006-11-28 11:58 | 踏雪赤兔

写得有点复杂，可以用STL简化代码。不过看得出，还是O(NlogN)的算法回复更多评论

# re: 寻找最长递增子序列

2006-11-28 16:18 | Charles

呵呵，因为这是准备面试用的，所以不能写成STL版的回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: Integer Partition 数1的个数 Fibonacci 简单打印内存的小玩意儿矩阵式螺旋输出求最大公约数与最小公倍数数内置类型的bit数计算Int最大最小值两个堆栈模拟一个队列检测补码表示

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2007年7月

日

一

二

三

四

五

六

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

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

积分与排名

积分 - 49500
排名 - 452

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜