Tags Math , Ruby
I've posted a new code snippet: lis_algorithms.rb - an implementation of 3 different algorithms for solving the Longest Increasing Subsequence problem. The implementations are:
  1. Using the the Longest Common Subsequence algorithm on a sequence with its sorted self: O(n^2)
  2. Using a dynamic programming algorithm described here . It is also O(n^2), but faster than (1) because of better constants and less generality.
  3. Using a greedy algorithm described here, that runs in O(n*log(n))