in reply to Puzzle: Longest Increasing Sequence
This is just a conversion to Perl of this pseudocode. It finds a Longuest Ascending Sequence in O(N log N). The sequence it happens to find is the first sequence when sorted numerically.
# Minimal Longest Ascending Subsequence
sub mlas {
my $n_las; # Length of output sequence
my @las; # Output sequence
my @terminals; # Array of terminals
my @backptrs; # Array of back pointers
$terminals[1] = 0;
$backptrs[0] = 1;
$n_las = 1;
for my $i (1..$#_) {
my $low = 1;
my $high = $n_las;
while ($low <= $high) {
my $mid = int(($low + $high) / 2);
if ($_[$i] <= $_[$terminals[$mid]]) {
$high = $mid  1;
} else {
$low = $mid + 1;
}
}
$terminals[$low] = $i;
if ($low <= 1) {
$backptrs[$i] = 1;
} else {
$backptrs[$i] = $terminals[$low  1];
}
if ($low > $n_las) {
$n_las++;
}
}
for (
my $i = $terminals[$n_las];
$i != 1;
$i = $backptrs[$i]
) {
unshift(@las, $_[$i]);
}
return @las;
}
{
my @a = (8, 6, 5, 1, 9, 3, 7, 4, 2, 10);
my @mlas = mlas(@a);
local $, = ", ";
local $\ = "\n";
print(@mlas); # 1, 3, 4, 10
}
{
my @a = (3, 10, 6, 1, 5, 7, 8, 2, 4, 9);
my @mlas = mlas(@a);
local $, = ", ";
local $\ = "\n";
print(@mlas); # 1, 5, 7, 8, 9
}
The page mentions a secant search would be faster than a binary search although the O() of would still be the same The O() would be slightly better, as noted by jdalbec.
Re^2: Puzzle: Longest Increasing Sequence by jdalbec (Deacon) on Apr 16, 2006 at 21:55 UTC 
Actually, O(n*log(n)**((sqrt(5)1)/2)) is strictly less than O(n*log(n)). The difference probably won't be noticeable for reasonable values of n, though, since log(n) grows so slowly anyway.  [reply] 

oh yeah. I thought it was *, not **
 [reply] 
Re^2: Puzzle: Longest Increasing Sequence by spurperl (Priest) on Apr 17, 2006 at 09:59 UTC 
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
 [reply] [d/l] [select] 

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] 
Re^2: Puzzle: Longest Increasing Sequence by demerphq (Chancellor) on May 16, 2006 at 19:11 UTC 
It finds a Longuest Ascending Sequence in O(N log N). The sequence it happens to find is the first sequence when sorted numerically.
I implemented a variant of this that will find all longest increasing sequences in the list.
It returns an iterator over all of the LAS'es in the list. The code contains an explanation of how it works.

$world=~s/war/peace/g
 [reply] [d/l] 
