So here´s the problem:
Given two sequences of number 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, 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 squared algorithm to solve this problem?
Thanks ahead.