注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

最长单调递增子序列  

2014-02-19 22:01:48|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


An个不同正整数构成的序列,求A的一个最长递增子序列。例如序列为1,5,3,8,10,6,4,9;它的最长递增子序列为1,5,8,101,5,8,9...

 

这是一道很典型的动态规划题目。设fi表示结尾元素为原序列中第i个元素的最

长单调递增序列的长度(为了简便,设a0 = -∞,f0= 0),动态规划的状态转移方程如下:

 

                                 

 最后所要求的结果就是{fi}中的最大值时间复杂度为0(n*n)

为了改进这个算法,我们需要引入一个辅助数组。设gi 表示到目前为止,所有长度为

的单调递增子序列中最后一个元素的最小值。易知,gi-1gi(1in)(可以用反证法来证明)

也就是说,{gi}是一个不下降序列。当到第i-1 个字符为止的{gi}已知时,fi 就等于在{gi}中第一个大于或等于ai 的元素的位置(也就是lower_bound() 所给出的位置)。然后,我们要对{gi}进行更新。更新十分简单,只要令gj=ai

就可以了。一开始,令gi =(1in)。由于

 

每次查找位置的时间复杂度为O(log n),而更新的时间复杂度为O(1),因此,这个算法总

的时间复杂度就是O(n log n).

改进后的算法(O(n log n))

 

 

fill(g, g + n, infinity);
for(int
 i = 0; i < n; i++) {
    int j = lower_bound(g, g + n, a[i]) - g;
    f[i] = j + 1;
    g[j] = a[i];
}

 fout << *max_element(f, f + n) << endl;

 

 

注: STL中的lower_bound()函数

如果被查找的值出现在序列中,那么lower_bound() 将返回序列中第一个和被查找的值

相等的元素的位置,而upper_bound() 将返回序列中最后一个和被查找的值相等的元素的后一个位置。这样的定义和STL 中序列的定义是一致的。设lower_bound() 的返回值为l

upper_bound() 的返回值为u,那么序列[l, u) 就是原序列中所有和被查找的值相等的元素所构成的子序列。如果被查找的值没有出现在序列中,那么lower_bound() upper_bound() 的返回值是相等的,都指向一个位置,使得如果把被查找的值插入到这个位置,序列仍然能够保持有序性

  评论这张
 
阅读(17)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018