隨筆 - 87 文章 - 279 trackbacks - 0

2006年1月

日

一

二

三

四

五

六

潛心看書(shū)研究！

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊(cè)

ACM OJ

HOJ
POJ
TOJ
URAL
UVA
ZOJ

My friends

搜索

積分與排名

積分 - 217765
排名 - 117

閱讀排行榜

評(píng)論排行榜

LIS O(nlogn)

const int MAXN = 100;

int d[MAXN];

int LIS(int *a, int n) {

int i, l, r, m, len;

for (i=1; i<=n; i++) {

if (a[i] >= d[len]) { //單調(diào)上升 a[i] > d[len]

len += 1;

d[len] = a[i];

} else {

l = 1;

r = len;

while (l < r - 1) {

m = (l + r) / 2;

if (d[m] <= a[i]) l = m; //單調(diào)上升 d[m] < a[i]

else r = m;

}

if (d[l] > a[i]) d[l] = a[i];

else d[r] = a[i];

}

return len;

}

posted on 2007-04-04 23:38 豪閱讀(1103) 評(píng)論(1) 編輯收藏引用所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法

FeedBack:

# re: LIS O(nlogn) 2011-07-30 15:39 cherryunix

len沒(méi)初值回復(fù) 更多評(píng)論

刷新評(píng)論列表

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

相關(guān)文章: 紅黑樹(shù)（數(shù)據(jù)結(jié)構(gòu)大作業(yè)擴(kuò)展版） pku3268 dij+heap 線段樹(shù)類 LIS O(nlogn) 凸包... MinHeap 樹(shù)狀數(shù)組 [轉(zhuǎn)貼] 快速計(jì)算某個(gè)日期是星期幾的經(jīng)驗(yàn)公式拓?fù)渑判?/a> 合并排序

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