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, which is executed in O(n²), 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.