Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
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..

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543634]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2018-02-25 00:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    When it is dark outside I am happiest to see ...














    Results (312 votes). Check out past polls.

    Notices?