首页 > 其他 > 详细

最长递减子序列(nlogn)(个人模版)

时间:2017-03-17 00:14:15      阅读:165      评论:0      收藏:0      [点我收藏+]

最长递减子序列(nlogn):

 1 int find(int n,int key)
 2 {
 3     int left=0;
 4     int right=n;
 5     while(left<=right)
 6     {
 7         int mid=(left+right)/2;
 8         if(res[mid]>key)
 9         {
10             left=mid+1;
11         }
12         else
13         {
14             right=mid-1;
15         }
16     }
17     return left;
18 }
19 
20 int Lis(int a[],int n)
21 {
22     int r=0;
23     res[r]=a[0];
24     r++;
25     for(int i=1;i<n;i++)
26     {
27         if(res[r-1]>a[i])
28         {
29             res[r]=a[i];
30             r++;
31         }
32         else
33         {
34             int loc=find(r,a[i]);
35             res[loc]=a[i];
36         }
37     }
38     return r;
39 }

 

最长递减子序列(nlogn)(个人模版)

原文:http://www.cnblogs.com/ECJTUACM-873284962/p/6562226.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!