# 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
}
[download]

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.