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

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

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


<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

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

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 49663
  • 排名 - 452

最新评论

阅读排行榜

评论排行榜