文档章节

最长单调上升子序列(LIS) O(nlogn)求法

o
 osc_wws45aot
发布于 2019/08/20 11:06
字数 573
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

常规的dp求LIS的时间复杂度为O(n2),对于n比较大的时候这是不能接受的。这时候我们就需要一个优秀的O(nlogn)的算法了。

这个算法是基于贪心的思想,具体来说就是开一个序列数组b,记录已经求得的“最长上升子序列”,当扫到一个元素大于序列b的最后一个元素时,就直接将扫到的元素加入序列b,否则就在b数组中二分查找第一个大于扫到的元素的元素,将其替换,因为这样序列的“潜力值”更大。

假设我们有一个序列{1,8,3,7,11,6,9,10}。
初始化b数组的第0个元素小于序列中的最小元素(比如0或-1,上次就被这个坑了)。
  扫描到值1,1大于b中第0个元素,此时b为{1}
  扫描到这8,8大于b末尾元素,此时b为{1,8}
  扫描到3,3小于b末尾元素,二分查找替换掉8,此时b为{1,3}
  扫描到7,直接加入,此时b为{1,3,7}
  扫描到11,直接加入,此时b为{1,3,7,11}
  扫描到6,小于末尾元素,二分查找替换掉7,此时b为{1,3,6,11}(此时b并不是按照a中的顺序来了)
  扫描到9,小于末尾元素,二分查找替换掉11,此时b为{1,3,6,9}
  扫描到10,直接加入,此时b为{1,3,6,9,10}

看完举的栗子,相信大家都多多少少明白,b中不一定记录的是a的单调上升序列,但是b数组的长度就是最长单调上升序列的长度了。

这里以POJ Longest Ordered Subsequence给出代码:

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int a[1001],b[1001];
 7 
 8 int n,len;
 9 int main(){
10     b[0]=-1;
11     scanf("%d",&n);
12     for(int i=1;i<=n;++i) scanf("%d",&a[i]);
13     for(int i=1;i<=n;++i){
14         if(a[i]>b[len]){
15             b[++len]=a[i];
16         }else{
17             int k=lower_bound(b+1,b+1+len,a[i])-b;
18             b[k]=a[i];
19         }
20     }
21     cout<<len;
22     return 0;
23 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Kotlin Class「T」

fun <T> gotoMainPage( context: Activity, postId: String, mainActivity: Class<T> ) { val intent = Intent(context, ADSplash......

osc_qatrfv06
26分钟前
9
0
小赢科技2020年一季报:由盈转亏1.96亿,M3以下贷款逾期率翻倍达6.71%

来源 | 新金融一线 北京时间6月29日,美股上市互金平台小赢科技公布了今年一季报未经审计的财务业绩报告。财报显示,该公司2020财年第一财季净营收同比下降31.9%至5.29亿元(人民币,下同);...

镭射财经
27分钟前
12
0
kotlin实现单例

/** * 功能:单例实现 */class Singleton private constructor() { companion object { val instance by lazy(mode = LazyThreadSafetyMode.SYNCHRONIZED) { Si......

osc_5nscij7v
27分钟前
11
0
七月算法机器学习 11 决策树、随机森林、 adaboost

目录 主要内容 决策树 信息增益 三种决策树学习算法 决策树的例子 决策树的过拟合 Bootstraping Bagging的策略 随机森林 提升的概念 Adaboost 举例 主要内容 决策树  决策树学习采用的是自...

osc_2718ydlo
28分钟前
10
0
支持千万人次毫秒级交易,360金融的系统性能如何做到?

提到“系统性能”问题,便立即联想到刚刚过去的“618”购物狂欢,电商公司在面对高密集度并发交易行为时,依托强大的系统性能以保持用户在网购与支付过程中平台的系统稳定性的极致案例。系统...

osc_jrhexi1r
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部