随笔 - 87 文章 - 279 trackbacks - 0

2006年2月

日

一

二

三

四

五

六

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

积分与排名

积分 - 211858
排名 - 116

阅读排行榜

评论排行榜

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]) { //单调上升 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; //单调上升 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 豪阅读(1068) 评论(1) 编辑收藏引用所属分类: 数据结构与算法

FeedBack:

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

len没初值回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。


相关文章: 红黑树（数据结构大作业扩展版） pku3268 dij+heap 线段树类 LIS O(nlogn) 凸包... MinHeap 树状数组 [转贴] 快速计算某个日期是星期几的经验公式拓扑排序合并排序

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理