Slow Solution

Time Complexity: $\mathcal O(N^2)$

See here.

Efficient Solution

In the $\mathcal O(N^2)$ solution, we increase the DP array only if $a[i] = b[j]$, but since both arrays are permutations of length $N$, for each $a[i]$, there must be only one matching element in $b$.

Let us create an array $pos$ where $pos[x]$ is the index of $x$ in $a$ ($a[pos[x]] = x$). Then, we can create another array, $c$ where $c[i]$ stores $pos[b[i]]$.

Notice that every increasing subsequence $x_{1 \dots k}$ in $c$ corresponds to a common subsequence between $a$ and $b$. Increasing subsequence $c[x_1], c[x_2], \dots c[x_k]$ corresponds to the the common subsequence $b[x_1], b[x_2], \dots b[x_k]$, which is equivalent to $a[c[x_1]], a[c[x_2]], \dots a[c[x_k]]$. Thus, the length of the longest common subsequence between $a$ and $b$ is the longest increasing subsequence of $c$.

Implementation

Time Complexity: $\mathcal O(N\log N)$

Copy
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# pos is the inverse of a
pos = [0] * (n + 1)
c = [0] * n