暴力求 LCS
可用 \(dp_{i,j}\) 表示第一个序列的前 \(i\) 位，第二个串的前 \(j\) 位的 LCS 的长度。显然有状态转移方程：
解释：如果当前的 \(P_i=P_j\)，那么有新的公共元素。我们可以选择新开一个子序列，或依附之前的子序列。
如果二者不相同，就只能继承前一个元素的 LCS 长度。
由于我们要把两个序列的每一对 \((i,j)\) 都枚举一遍，所以时间复杂度为 \(\Theta(n^2)\)。
但是，这个算法不能通过这一题。（不过这题是可以的，只要稍作魔改就可以了。）
（特殊）优化
LCS 转化为 LIS
因为本题中保证 \(P_1,P_2\) 分别为 \(1,2,\dots,n\) 的两个排列，所以，\(P_1\) 中的每个元素都可以在 \(P_2\) 中找到。
而公共子序列只要保证在两序列中的顺序一样。
所以，我们可以用一个映射数组（记为 \(m\)）把 \(P_2\) 中的数按 \(P_1\) 中的顺序进行编号。
然后问题就被转化成了求 \(m\) 的 LIS 长度，求出它即可。
时间复杂度即为求 LIS 的复杂度。如用二分求，为 \(\Theta(n\log n)\)，可过。
二分求 LIS
本部分将简要介绍 LIS 的 \(\Theta(n\log n)\) 求法。
如已学过，请忽略。
令 \(g_i\) 表示在该序列中，长度为 \(i\) 的 LIS 的末尾数的最小值。显然，\(g_1=a_1\)，且 \(g\) 数组有一个重要性质：单调不减。
而之后的 \(g_2,g_3,\dots,g_n\) 就等于 \(g\) 数组中对应的 LIS 长度小于它且对应的 \(g\) 值大于等于当前位置的数的第一个位置。由于 \(g\) 数组有单调性，所以这个位置可以二分到。
即 \(g_i = g_{i'}\)，其中 \(i'\) 表示符合上述条件的下标。
实现
（只给出输入和算法实现，不可直接编译）
struct N {int data, id;
};
N a[MAXN], b[MAXN];
int m[MAXN], g[MAXN], n, ans = 0;
int main() { cin >> n;for(int i=1; i<=n; ++i){cin >> a[i].data;m[a[i].data] = i;a[i].id = i;}for(int i=1; i<=n; ++i){cin >> b[i].data;b[i].id = i;}memset(g, 0x77, sizeof g);g[1] = a[1];for(int i=1; i<=n; ++i){int x = m[b[i].data];int pos = lower_bound(g+1, g+n+1, x) − g;ans = max(ans, pos);g[pos] = min(x, g[pos]);}cout << ans;return 0;
}