Do you know where your variables are? PerlMonks

### Comment on

 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!
• 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.
• 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
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (10)
As of 2018-05-22 14:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (163 votes). Check out past polls.

Notices?