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

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

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


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

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

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 47992
  • 排名 - 455

最新评论

阅读排行榜

评论排行榜