随笔 - 87  文章 - 279  trackbacks - 0
<2007年8月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214423
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

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 阅读(1084) 评论(1)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: LIS O(nlogn) 2011-07-30 15:39 cherryunix
len没初值  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理