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
`