So here´s the problem:
Given two sequences of numbers s and r, such that all elements from the sequences are distinct, find the longest common subsequence of both sequences.
Now, i know the DP solution for the general case, which is executed in O(n2), but in this problem i need to get as efficient as O(nlg(n)). I found an explanation on stack overflow about how to use the LIS (Longest Increasing Subsequence) algorithm to achieve this complexity, but i didn´t understand very well. So does anyone how to explain a faster than quadratic algorithm to solve this problem?
Thanks ahead.
Since the elements are distinct we can fix one sequence, let V[i] be the i-th sequence and inV[i][j] is the position of the element with value j in the i-th sequence, the dp is straightforward i guess, dp[K] = max(dp[W] + 1 ) such that W > K && inV[1][V[0][W]] > inV[1][V[0][K]] ) or, dp[K] means the LCS of a sequence with V[0][K] as last element so we can use a segment tree with RMQ to solve this, since the restriction is inV[1][V[0][W]] > inV[1][V[0][K]] we can add dp[X] in the position inv[1][V[0][X]] and dp[Y] will be RMQ in range (inV[1][V[0][Y]] , inf)
Edit: My mistake. Sorry.
r: 2 3 s: 3 2 What's your answer for this one?
Sorry, I forgot about that. Thanks for pointing it out :)
You can use fenwick tree. Go from left to right in second array. For each elemnt find occurence in first array (let's say that this posision is X, this can be found with the help of maps). Now you just have to find maximum value from 1 to X-1 in our BIT which is not hard. Let's say answer is P. Than add P+1 in fenwick starting from position X.