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++;
      }

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

[download]

In reply to Re^2: Puzzle: Longest Increasing Sequence by spurperl
in thread Puzzle: Longest Increasing Sequence by TedPride

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.