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://www.toymoban.com/news/detail-793925.html
(看来我要重新理解下二分查找了)文章来源地址https://www.toymoban.com/news/detail-793925.html
到了这里,关于[ACM 学习] 最长上升子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!