如何计算 LIS
2022/7/31 23:39:22
本文主要是介绍如何计算 LIS,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LIS,即最长上升子序列 .
基于 DP 的做法
令 \(dp_i\) 表示以 \(i\) 结尾的 LIS 长度,则有
\[dp_i=1+\max_{\substack{j<i\cr a_j<a_i}}\{dp_j\} \]可以直接暴力转移,于是答案就是 \(\displaystyle\max_{i\in[1,n]}dp_i\) .
时间复杂度 \(O(n^2)\) .
优化方法(均为 \(O(n\log n)\)):
- 线段树优化:直接线段树优化取 max .
- ST 表优化:只有最后加一个数,所以 ST 表的倍增数组只用修改 log 个 .
- 树状数组优化:因为只有最后加一个数和后缀 max,所以可以树状数组 .
代码非常平凡,略(外链:link)
贪心
扫一遍,考虑维护两个东西,\(ans,len\),分别表示目前的 LIS 和以目前端点为结尾的 LIS,同时维护目前的 LIS 数组 .
于是每次加一个数,如果更优直接加进去,否则修改原 LIS 数组修改 \(len\),这样 \(ans\) 永远最优 .
时间复杂度 \(O(n\log n)\) .
可能比较魔幻,感性理解吧,,
核心代码,来自 Eafoo .
int main() { int n = read(); for (int i = 1; i <= n; ++i) num[i] = read(), lis[i] = -inf; int tot = 0; for (int i = 1; i <= n; ++i) { if (num[i] >= lis[tot]) lis[++tot] = num[i]; else *upper_bound(lis + 1, lis + tot + 1, num[i]) = num[i]; } printf("%d\n", tot); }
这篇关于如何计算 LIS的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行