Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
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 having an uproarious good time at the Monastery: (7)
As of 2014-09-20 11:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (158 votes), past polls