最长上升子序列 O(nlogn)
2024-10-21 09:39:07
题意:求一个序列中的最长上升子序列。
平常我用的是N*N做法,但是一遇到需要nlogn时,就被卡的无地自容了。
所以下定决心要学习nlogn做法。
如何实现nlongn哪?
这里要用到一个栈B,记录按照时间顺序输入的一个上升子序列。
每输入一个数a就放入栈中,如果a>B[top] ,就放在下一位(B[++top]=a)
如果a<B[top],在栈中找到一个最小的大于等于a的b,(找到一个下限)。让栈内部的数更新变小,以期装更多的数。
最后栈的高度就是最长上升子序列的长度。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
int maxn,n,a[],B[],cnt;
int find(int x)
{
int l,r,mid;
l=,r=cnt;
while(l<=r)
{
mid=(l+r)/;
if(B[mid]>=x) r=mid-;
else l=mid+;
}
return l;
}
int main()
{
// freopen("sort.in","r",stdin);
// freopen("sort.ans","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]); B[]=-;cnt=;
for(int i=;i<=n;i++)
{
if(a[i]>B[cnt]) B[++cnt]=a[i];
else{
int t=find(a[i]);
B[t]=a[i];
}
} cout<<cnt;
return ;
}
代码
最新文章
- Docker 总结(转载)
- How to convert any valid date string to a DateTime.
- 使用Oracle ODP.NET 11g的.NET程序发布方法
- redmine安装部署
- sprintf的缓冲区溢出问题
- Android SDK安装教程
- hdu----(1528)Card Game Cheater(最大匹配/贪心)
- Servlet &; JSP - Filter
- MIPI D-PHY 简写收集
- chrome扩展,如何阻止浏览自动关闭桌面通知.
- http工具类
- Python并发编程协程(Coroutine)之Gevent
- 201521123036 《Java程序设计》第8周学习总结
- 移动端与PHP服务端接口通信流程设计(增强版)
- UWP上可用的GB2312编码
- Win10命令大全通用(Win8,Win7)
- Lintcode221 Add Two Numbers II solution 题解
- [LeetCode] Relative Ranks 相对排名
- Easy Finding POJ - 3740 (DLX)
- 几个dos命令