Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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.


In reply to Re: Puzzle: Longest Increasing Sequence by ikegami
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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others studying the Monastery: (3)
    As of 2014-09-23 02:36 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (210 votes), past polls