Syntactic Confectionery Delight PerlMonks

### Re: Puzzle: Longest Increasing Sequence

by BrowserUk (Pope)
 on Apr 16, 2006 at 11:05 UTC ( #543634=note: print w/replies, xml ) Need Help??

in reply to Puzzle: Longest Increasing Sequence

```#! perl -slw
use strict;

sub lis {
my( \$aoa ) = [[ pop @_ ]];
for my \$n ( reverse @_ ) {
\$n < \$_->[0] and push @\$aoa, [ \$n, @\$_ ] for @\$aoa;
push @\$aoa, [ \$n ];
}
my \$r = pop @\$aoa;
@\$_ > @\$r and \$r = \$_ for @\$aoa;
return @\$r;
}

my @t1 = ( 8, 6, 5, 1, 9, 3, 7, 4, 2, 10 );
my @t2 = ( 3, 10, 6, 1, 5, 7, 8, 2, 4, 9 );

print "\n@t1";
print join ' ', lis @t1;

print "\n@t2";
print join ' ', lis @t2;

__END__
c:\test>543621-2

8 6 5 1 9 3 7 4 2 10
1 3 4 10

3 10 6 1 5 7 8 2 4 9
1 5 7 8 9

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: Puzzle: Longest Increasing Sequence
by ivancho (Hermit) on Apr 16, 2006 at 18:54 UTC
that's exponential, unfortunately. Try it on a sorted array, and you'll end up going through all possible subsequences.

Update: not to mention that you'll run out of memory on a list longer than 20 elements..

Create A New User
Node Status?
node history
Node Type: note [id://543634]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (7)
As of 2018-08-16 13:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Asked to put a square peg in a round hole, I would:

Results (167 votes). Check out past polls.

Notices?