最长上升序列的O(nlogn)求法

网友投稿 651 2022-11-20 18:15:00

最长上升序列的O(nlogn)求法

d数组:

d[i]表示长度为i的最长上升序列的末尾的最小值

显然d数组单调递增

于是每插入一个i,我们二分找小于它且最大的

假设为d[l]

d[l]a

因为a可以接在l后面构成长度为l+1,结尾为a的最长上升序列

所以讲d[l+1] 更新成a

答案为tail

#include#define N 100005using namespace std;int n,d[N],tail,ans;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int a;scanf("%d",&a); int l=0,r=tail; while(l>1; if(a>d[mid]) l=mid; else r=mid-1; } if(l>=tail) tail++; d[l+1]=a; } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：序列
上一篇:关于Mybatis使用collection分页问题
下一篇:数字游戏[线性筛]
相关文章