首先考虑动态规划，a[i]==b[j]，f[i][j]=f[i-1][j-1]+1,否则 f[i][j]=max(f[i-1][j],f[i][j-1]);然后看了一眼数据范围，被卡的实施的，然后考虑优化，看到题目是一个排列于是不要考虑重复的问题，于是只在b里看，如果b[i]在a中的位置，小于我们维护的最长的就不行，否则的话直接加入我们维护的最长子序列的长度。就像贪心+二分找最长上升子序列一样。
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 100005
const double PI = 3.14159265358979323846;
using namespace std;
int n, a[N], b[N],f[N],ma[N];//ma数组记录每个元素在a中的位置
signed main()
{
ios;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ma[a[i]] = i;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
f[i] = INF;
}
int len = 0;//当前最长子序列的长度
f[0] = 0;//开始状态
for (int i = 1; i <= n; i++)
{
int l = 0, r = len, mid;
if (ma[b[i]] > f[len])f[++len] = ma[b[i]];//出现的位置在后面
else
{
while (l < r)//找到第一个大于等于ma[b[i]]的位置
{
mid = l + r >> 1;
if (f[mid] > ma[b[i]]) r = mid;
else l = mid + 1;
}
}
f[l] = min(ma[b[i]], f[l]);
}
cout << len << endl;
return 0;
}