Find the longest increasing subsequence

Please know the answer for my interviews ;-) A subsequence is made up of non contiguous symbols. A solution can be found in O(n * log n), where n is the length of the string S[1...n] by using binary search