Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

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).

---
$world=~s/war/peace/g


Comment on Re: Puzzle: Longest Increasing Sequence
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2014-12-27 12:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (177 votes), past polls