[ACM 学习] 最长上升子序列

发布时间:2024年01月16日

LIS(最长上升子序列)的三种经典求法 - 一只不咕鸟 - 博客园 (cnblogs.com)

理解一下第三种方法(贪心+二分查找)

因为构建的是上升子序列,所以是可以用二分查找找到最大的小于当前 A[i] 的在子序列中的 F[j],并更新 F[j+1]

注:刚开始看的时候还在疑惑只换一个的话,后面的那些怎么办,后来发现,其实我们想要的只是长度,不关注子序列的具体数字,换下来并不影响已记录的最长长度,并且,还为后面提供了更长的可能(贪心思想:更小的元素可以接更多的)

这段二分查找的代码也很有意思,只要还是 a[i] 小于等于f[mid](为什么包括等于,因为对于严格小于来说,等于还是大了),就到左边去,最后 l 的位置会在严格小于 a[i] 的元素下一个坐标那(出while是因为 l>r 所以要想想是要l的数还是r的数,作为比较的数可以理解成大小在 l 与 r 中间)。

(看来我要重新理解下二分查找了)

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135613309
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。