posts - 71,  comments - 41,  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 阅读(1419) 评论(3)  编辑 收藏 引用 所属分类: 面试小算法

FeedBack:
# re: 寻找最长连续递增子序列
2006-11-22 12:55 | chenger
都可以用动态规划解决，不需要回溯  回复  更多评论
  
# re: 寻找最长连续递增子序列
2006-11-22 15:57 | Charles
呵呵，笔误  回复  更多评论
  
# re: 寻找最长连续递增子序列
2011-06-23 14:36 | 大物
这个只能算是方法，效率太低了  回复  更多评论
  

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


Copyright ©2024 Charles Powered By: 博客园 模板提供：沪江博客
<2007年7月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

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

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 49500
  • 排名 - 452

最新评论

阅读排行榜

评论排行榜