题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1000000+100;
int id[N],q[N];
int main()
{
int n;cin>>n;
memset(id, -1, sizeof id);
for (int i = 0; i < n; i ++ ){
int x;scanf("%d",&x);id[x]=i;
}
int tt=0;//最长子串长度,用作二分查找的范围
q[0]=-1;//哨兵,q数值存放x长度的串末尾最小元素
for (int i = 0; i < n; i ++ ){
int x;scanf("%d",&x);
int k=id[x];
if(k==-1)continue;
int l=0,r=tt+1;
//二分查找第一个小于枚举元素的位置修改该位置的下一位(查找第一个大于该元素的位置)
while(l<r){
int mid=(l+r)>>1;
if(q[mid]<k)l=mid+1;
else r=mid;
}
q[l]=k;
tt=max(tt,l);//确定新的范围
}
cout<<tt<<endl;
}