http://www.perlmonks.org?node_id=543792


in reply to Re: Puzzle: Longest Increasing Sequence
in thread Puzzle: Longest Increasing Sequence

Just for kicks, here is the same implemented in Ruby. I noticed that the original page has a bug you fixed - towards the end of the main loop, there is:
if ($low > $n_las) { $n_las++; }
While in the pseudocode it's "if (low .ge. n_as) n_as += 1" and I presume .ge. means "greater or equal" ?!

Anyways, here's my implementation. It is notably cleaner than yours, but twice slower:

def find_lis_greedy(seq) n = seq.length terminals = [0] * (n + 1) backptrs = [-1] + [0] * (n - 1) lis = [] n_lis = 1 1.upto(n - 1) do |i| low = 1 high = n_lis while low <= high mid = (low + high) / 2 if seq[i] <= seq[terminals[mid]] high = mid - 1 else low = mid + 1 end end terminals[low] = i if low <= 1 backptrs[i] = -1 else backptrs[i] = terminals[low - 1] end n_lis += 1 if low > n_lis end lis[n_lis - 1] = seq[terminals[n_lis]] temp = terminals[n_lis] (n_lis - 2).downto(0) do |i| temp = backptrs[temp] lis[i] = seq[temp] end return lis end