The problem can be reduced to computing Longest Common Subsequence between both arrays.

Since one of the arrays has distinct elements, we can consider that these elements describe an arrangement of numbers, and we can replace each element in the other array with the index it appeared at in the first array.

Then the problem is converted to finding Longest Increasing Subsequence in the second array, which can be done in O(n log n).