posts - 71, comments - 41, trackbacks - 0

尋找最長(zhǎng)遞增子序列

注意，不一定連續(xù)遞增

template < class ?T > ?

int ?FindLIS(T? * arr,? int ?len,?T? *& result)

{

???? int ? * last? = ? new ? int [len]();

???? int ? * track? = ? new ? int [len]();

???? int ?left,?right,?mid;

???? int ?iCurrMaxLen? = ? 0 ;

???? if ?(len? < ? 1 )

???? {

????????result? = ? 0 ;

???????? return ? 0 ;

????}

????result? = ? 0 ;

????last[ 0 ]? = ? 0 ;

???? for ?( int ?i? = ? 1 ;?i? < ?len;?i ++ )?

???? {

???????? if ?(arr[last[iCurrMaxLen]]? < ?arr[i])

???????? {

????????????track[i]? = ?last[iCurrMaxLen];

????????????last[ ++ iCurrMaxLen]? = ?i;

???????????? continue ;

????????}

????????left? = ? 0 ;

????????right? = ?iCurrMaxLen;

???????? while ?(left? < ?right)

???????? {

????????????mid? = ?(left? + ?right)? / ? 2 ;

????????????arr[last[mid]]? < ?arr[i]? ? ?left? = ?mid? + ? 1 ?:?right? = ?mid;

????????}

???????? if ?( /* left?<=?right?&&? */ arr[i]? < ?arr[last[left]])?

???????? {

???????????? if ?(left? > ? 0 )?

????????????????track[i]? = ?last[left? - ? 1 ];

????????????last[left]? = ?i;

????????}

????} // for

???? for ?(left? = ?iCurrMaxLen,?right? = ?last[iCurrMaxLen];?left? >= ? 0 ;?left -- ,?right? = ?track[right])

????????last[left]? = ?arr[right];

???? if ?(track)

???? {

????????delete?[]?track;

????????track? = ? 0 ;

????}

????result? = ?last;

????last? = ? 0 ;

???? return ?iCurrMaxLen? + ? 1 ;

}

稍微解釋一下，last中存的是所有i長(zhǎng)度子序列中l(wèi)ast[i]最小的那個(gè)值。而track中記錄它的前一個(gè)值。這樣可以沿著track找回去。

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

FeedBack:

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

2006-11-28 11:58 | 踏雪赤兔

寫(xiě)得有點(diǎn)復(fù)雜，可以用STL簡(jiǎn)化代碼。不過(guò)看得出，還是O(NlogN)的算法回復(fù) 更多評(píng)論

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

2006-11-28 16:18 | Charles

呵呵，因?yàn)檫@是準(zhǔn)備面試用的，所以不能寫(xiě)成STL版的回復(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 管理

2007年7月

日

一

二

三

四

五

六

決定開(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)論排行榜