posts - 71, comments - 41, trackbacks - 0

尋找最長(zhǎng)連續(xù)遞增子序列

注意是連續(xù)遞增
比如，"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;

}

還有一種比較難的就是非連續(xù)遞增子序列，這個(gè)得用到回溯薄記，下篇貼

posted on 2006-11-22 12:24 Charles 閱讀(1452) 評(píng)論(3) 編輯收藏引用所屬分類(lèi): 面試小算法

FeedBack:

# re: 尋找最長(zhǎng)連續(xù)遞增子序列

2006-11-22 12:55 | chenger

都可以用動(dòng)態(tài)規(guī)劃解決，不需要回溯回復(fù) 更多評(píng)論

# re: 尋找最長(zhǎng)連續(xù)遞增子序列

2006-11-22 15:57 | Charles

呵呵，筆誤回復(fù) 更多評(píng)論

# re: 尋找最長(zhǎng)連續(xù)遞增子序列

2011-06-23 14:36 | 大物

這個(gè)只能算是方法，效率太低了回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: Integer Partition 數(shù)1的個(gè)數(shù) Fibonacci 簡(jiǎn)單打印內(nèi)存的小玩意兒矩陣式螺旋輸出求最大公約數(shù)與最小公倍數(shù) 數(shù)內(nèi)置類(lèi)型的bit數(shù) 計(jì)算Int最大最小值兩個(gè)堆棧模擬一個(gè)隊(duì)列檢測(cè)補(bǔ)碼表示

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

2006年11月

日

一

二

三

四

五

六

決定開(kāi)始寫(xiě)工作日記，記錄一下自己的軌跡...

常用鏈接

留言簿(4)

隨筆分類(lèi)(70)

隨筆檔案(71)

charles推薦訪問(wèn)

Code Project
Linux Journal
Linux man pages
Single UNIX Specification
電子書(shū)1
電子書(shū)2
電子書(shū)3

常用鏈接

留言簿(4)

隨筆分類(lèi)(70)

隨筆檔案(71)

charles推薦訪問(wèn)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜