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
Re^3: Puzzle: Longest Increasing Sequence by ikegami (Pope) on Apr 17, 2006 at 16:41 UTC 
It is indeed a bug fix, not a typo.
The other thing I did was to clean up the code that builds the return value by using unshift. I no longer needed a counting loop, so I removed the counter variable ("i") and replaced the counting loop with a while loop (implemented as a for loop). "temp" was a bad name — even i, j, etc would be better since temp holds an index — so I renamed it to "i".
 [reply] [d/l] 
