Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Re: Puzzle: Longest Increasing Sequence

by demerphq (Chancellor)
on Apr 16, 2006 at 21:59 UTC ( #543707=note: print w/ replies, xml ) Need Help??

in reply to Puzzle: Longest Increasing Sequence

Heres my go. Originally I had something that was performing between 2N-1 and N*((N+1)/2), but kaif provided the insight I needed to get it to N log N when he pointed out that you only need to store one path of a given length at any one time.

BTW, I wanted a single routine that could return either the indexes or the actual values, so this is a little clunkier than it need be if you didnt care about the indexes.

Update: I was wrong, the worse case run time for this routine is (N+1)/2*N, which is O(N2).


Comment on Re: Puzzle: Longest Increasing Sequence
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543707]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2015-10-04 16:17 GMT
Find Nodes?
    Voting Booth?

    Does Humor Belong in Programming?

    Results (103 votes), past polls