posts - 71, comments - 41, trackbacks - 0

計(jì)算最長遞增子序列的長度

template < class ?T >

int ?GetLISLen(T? * arr,? int ?n)

{

???? if ?(n? < ? 1 )

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

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

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

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

????

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

????

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

???? {

???????? if ?(arr[i]? >= ?last[iCurrMaxLen])

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

???????? else ? if ?(arr[i]? < ?last[ 0 ])

????????????last[ 0 ]? = ?arr[i];

???????? else

???????? {

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

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

???????????? while ?(left? != ?right? - ? 1 )

???????????? {

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

????????????????(last[mid]? <= ?arr[i])? ? ?(left? = ?mid)?:?(right? = ?mid);

????????????}

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

????????} // if

????????

????} // for

???? for ?( int ?i? = ? 0 ;?i? < ?iCurrMaxLen? + ? 1 ;?i ++ )

???? {

????????printf( " %d " ,?last[i]);

???????? if ?(i? != ?iCurrMaxLen)

????????????printf( " \x20 " );

???????? else

????????????printf( " \n " );

????}

???? if ?(last)

???? {

????????delete?[]?last;

????????last? = ? 0 ;

????}

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

}

posted on 2006-11-22 17:45 Charles 閱讀(561) 評論(0) 編輯收藏引用所屬分類: 面試小算法

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

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

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

2006年11月

日

一

二

三

四

五

六

決定開始寫工作日記，記錄一下自己的軌跡...

常用鏈接

留言簿(4)

隨筆分類(70)

隨筆檔案(71)

charles推薦訪問

Code Project
Linux Journal
Linux man pages
Single UNIX Specification
電子書1
電子書2
電子書3

常用鏈接

留言簿(4)

隨筆分類(70)

隨筆檔案(71)

charles推薦訪問

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜