Longest common subsequence

general
,
1

I encountered this as a sub problem few months back while doing some problems.

Given 2 arrays constituting the permutation of numbers from 1 to N. We need to find the longest common subsequence of these 2 arrays.

1 <= N <= 500000

I think it will be a good question to fit at position 3. What do you guys think?

2

As you mentioned,this is exactly a sub problem of last year’s gwalior regional qn. I don’t think it is good to ask same qn from a recent contest. Anyway we can ask this if we are short of qns.

1 Like
3

I think this is a standard sum. I saw this in couple of contests so far. This or similar variation - couple of arrays, sort one, get LIS on other kind of.