最新消息:点击查看大S的省钱秘笈

最长上升子序列(LIS)长度的O(nlogn)算法

编程相关 Slyar 687浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

刚才用O(n^2)的DP算法做了最长上升子序列,具体见POJ2533解题报告。后来在网上看到说LIS问题有O(nlogn)的算法,于是拿来小研究了一下。

这个算法其实已经不是DP了,有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n),每次计算要查找N次还是O(n),一共就是O(n^2);现在搜索换成了O(logn)的二分搜索,总的复杂度就变为O(nlogn)了。

这个算法的具体操作如下(by RyanWang):

开一个栈,每次取栈顶元素top和读到的元素temp做比较,如果temp > top 则将temp入栈;如果temp < top则二分查找栈中的比temp大的第1个数,并用temp替换它。 最长序列长度即为栈的大小top。

这也是很好理解的,对于x和y,如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y],此时的最长序列长度没有改变但序列Q的''潜力''增大了。

举例:原序列为1,5,8,3,6,7

栈为1,5,8,此时读到3,用3替换5,得到1,3,8; 再读6,用6替换8,得到1,3,6;再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。

用该算法完成POJ2533的具体代码如下:

转载请注明:Slyar Home » 最长上升子序列(LIS)长度的O(nlogn)算法

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (22)

  1. 要求LIS的方案用个SGT维护一下DP就可以啦。
    Grcc3年前 (2013-11-26)回复
  2. 我觉得这样求 下界和上界略麻烦,不如用stl里的upper_bound和lower_bound!
    柳qing3年前 (2013-06-30)回复
  3. 啊。。。我错了。。。这个算法是正确的。。。
    土豆地瓜天使4年前 (2013-05-28)回复
  4. 晕 本来就是用数组来模拟栈
    skillart4年前 (2013-03-18)回复
    • 我也晕,我知道是用数组来模拟栈,只是这个命名方式不合适,很容易令人认为是栈。
      robin4年前 (2013-03-18)回复
  5. 楼主 你的算法写的很好。但注释错了。 /* 二分检索栈中比temp大的第一个数 */, 你的代码写的是查找不小于temp的第一个数。 比如1 2 3 4 5 6 4 最后一个数字是temp=4 之前的stack是 1 2 3 4 5 6 理论上来讲比temp大的第一个数字应该是5 你的结果是4.事实上本题的确就应该如此,只是你的注释错了。
    skilart4年前 (2013-03-18)回复
  6. 人家博主也没说能够直接找到结果序列啊?这个方法仅可以用作找出最长上升子序列的长度是多少,至于最终的序列是什么,这个方法应该是不行的。还需要动态规划。
    fxp4年前 (2012-10-05)回复
  7. 如果需要输出 LIS 的解,还能保证 n log(n) 的算法复杂度吗?
    Jing4年前 (2012-09-19)回复
  8. 竟然起个stack名字的数组,害我以为是个栈。 但是很奇怪,同样是用数组,你的程序用来解POJ2533怎么比我的慢呢?
    shilong5年前 (2011-09-09)回复
  9. 其实用个数组就OK了,没必要用栈
    shilong5年前 (2011-09-08)回复
  10. 终于明白了,其实这个注释/* 二分检索栈中比temp大的第一个数 */是有一点问题, 因为如果栈中有一个数与temp一样大呢?这时就不需要更新栈中的值。 但博主采用的算法还是让它继续运行,最后结果是如果栈中有一个值比如说是stack[i] == temp, 它仍然会执行stack[i] = temp. 如果栈中没有值等于temp,则找到位置stack[i] < temp < stack[i + 1], 然后stack[i + 1] = temp. 这个算法果然比O(n^2)的快,
    shilong5年前 (2011-09-08)回复
  11. 前面那几个家伙也真是的,这个算法只是用来求最长递增子序列的长度的, 并不能用来求最长递增子序列。 看来二分查找还是有一点难写。我写了好多次都错了。 如果是if (temp >= stack[mid])的话,这个程序对于以下这个测试用例得到的结果是4. test case: 5 1 4 5 4 5
    shilong5年前 (2011-09-08)回复
  12. 二分查找部分确实有误:low=high时,可以跳出;temp>=stack[mid]时才可以舍去[low,mid]。 思路很好。
    Len5年前 (2011-08-03)回复
  13. 算法没有问题 表述是错的 你的代码写的是2分查找>=temp的那个值不是>temp的那个值,实际上应该也是这样 你的表述说的是"二分查找栈中的比temp大的第1个数,并用temp替换它",包括代码注释也是错的 如果是大于temp的二分查找应该是这样的 if (temp >= stack[mid]) test case: 5 1 4 5 4 5 但是。。。。POJ 2个都能过 数据弱
    leonard6年前 (2011-04-11)回复
  14. @浪费时间 我就很奇怪你们这些人。。。就不知道看清楚再说么。。。我都说这个算法是求长度的了。。。无语。。。
    Slyar6年前 (2011-03-22)回复
  15. 简直误人子弟。。。这个算法是错的。。。。 但例子若为1,5,8,3,最后得到的是1,3,8,不是最长递增子序列了 正确的算法是用nlogn的先排序,然后比彼此的index。。。
    浪费时间6年前 (2011-03-22)回复
  16. 这个算法好
    nizhenyang6年前 (2010-09-06)回复
  17. @Paul a[]在算法结束后记录的并不是一个符合题意的最长上升子序列 它只是存储的对应长度LIS的最小末尾。
    匿名6年前 (2010-08-30)回复
  18. @perfectgeorge 最先出现的哪一个
    Slyar7年前 (2010-05-29)回复
  19. 最长上升子序列如果有多个,那么这样写栈里面的那个是哪一个?
    perfectgeorge7年前 (2010-05-29)回复
  20. @Paul 唔,这个算法本来就是为了求最长上升子序列的"长度"的...
    Slyar7年前 (2009-12-11)回复
  21. 引用: “举例:原序列为1,5,8,3,6,7 栈为1,5,8,此时读到3,用3替换5,得到1,3,8; 再读6,用6替换8,得到1,3,6;再读7,得到最终栈为1,3,6,7。最长递增子序列为长度4。” 恩,确实可以得到最长递增子序列的长度;但例子若为1,5,8,3,最后得到的是1,3,8,不是最长递增子序列了。是不是需要稍微改进一下?
    Paul7年前 (2009-12-11)回复