O(n log n)求最长上升子序列与最长不下降子序列
2024-09-07 14:02:29
考虑dp(i)表示新上升子序列第i位数值的最小值.由于dp数组是单调的，所以对于每一个数，我们可以二分出它在dp数组中的位置，然后更新就可以了，最终的答案就是dp数组中第一个出现正无穷的位置。
代码非常简单：
for(int i=;i<n;i++)dp[i]=oo;
for(int i=;i<n;i++)*lower_bound(dp,dp+n,A[i])=A[i];
printf("%d\n",(lower_bound(dp,dp+n,oo)-dp));
如果是最长不下降子序列的话只需要把第二行的lower_bound改成upper_bound就可以了。
如果是最长下降子序列或者最长不上升子序列的话只需要把原序列倒过来做一遍就好了。
最新文章
- [LeetCode] Walls and Gates 墙和门
- ubuntu 14.04 ns2.35 ***buffer overflow detected **: ns terminated解决办法
- Nodejs 高并发长链接TCP链接的服务器设计问题
- django开发个人简易Blog——构建项目结构
- Android自动化测试 - 自动化测试工具比较
- 远程桌面Default.rdp 中各个参数的含义（转）
- java初始化构造函数调用顺序
- HashMap存值
- vmdk虚拟机转换为OVF模板，导入esxi
- DataGridView点击排序完成后如何禁止自动排序
- 用canvas 绘制的饼状统计图、柱状统计图、折线统计图
- C#中指针使用总结
- jquery uploadifive使用
- poi做Excel数据驱动,支持.xls和.xlsx格式的excel文档，比起jxl强大不少
- 试水 Egret ：TouchEvent与EnterFrame相关
- 友坚恒天.开发板（Cotex-A9 Exynos4412 开发板）
- Project下载提示检索 COM 类工厂中 CLSID 为 {36D27C48-A1E8-11D3-BA55-00C04F72F325} 的组件失败
- Intellj IDEA常用快捷键
- vue基础学习（二）
- 常用数学符号的 LaTeX 表示方法