posts - 71, comments - 39, trackbacks - 0

寻找最长连续递增子序列

注意是连续递增
比如，"12345367889abcdefghij123" -> "abcdefghij"

template < class T >

int FindLongestConIncSubseq( const T * arr, int n, int * pos)

{

int start = 0 , end = 1 ;

int iMaxLen = 1 , iCurrLen = 1 ;

for (end = 1 ; end < n; end ++ )

{

if (arr[end] >= arr[end - 1 ])

{

iCurrLen ++ ;

}

else

{

if (iCurrLen > iMaxLen)

{

iMaxLen = iCurrLen;

start = end - iMaxLen;

}

iCurrLen = 1 ;

}

} // for

if (iCurrLen > iMaxLen)

{

iMaxLen = iCurrLen;

start = end - iMaxLen;

}

* pos = start;

return iMaxLen;

}

还有一种比较难的就是非连续递增子序列，这个得用到回溯薄记，下篇贴

posted on 2006-11-22 12:24 Charles 阅读(338) 评论(2) 编辑收藏引用所属分类: 面试小算法

FeedBack:

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

2006-11-22 12:55 | chenger

都可以用动态规划解决，不需要回溯回复更多评论

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

2006-11-22 15:57 | Charles

呵呵，笔误回复更多评论

刷新评论列表

标题

姓名

主页


验证码	*

内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)

Remember Me?

登录使用高级评论新用户注册返回页首恢复上次提交

[使用Ctrl+Enter键可以直接提交]

常用链接

留言簿

随笔分类(70)

随笔档案(71)

相册

charles推荐访问

搜索

积分与排名

积分 - 20270
排名 - 125

常用链接

留言簿

随笔分类(70)

随笔档案(71)

相册

charles推荐访问

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜