An algorithm for the determination of a longest increasing subsequence in a sequence

AbstractWe present a simple, novel and efficient algorithm for the determination of a longest increasing subsequence in a given sequence of n numbers. Our algorithm performs in O(nlog r) time in the worst case, where r is the size of the output, i.e. r is the length of the longest increasing subsequence (s). The algorithm is motivated by the idea of a Young tableau that is associated with a given sequence