# 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 }