Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543707]
help
Chatterbox?
[choroba]: needed everywhere, available rarely
[LanX]: Question: starting a script from an icon in Windows, but after C-c the window closes ... what I want is to restart in the cmd.exe. Recommendations?
[Corion]: LanX: What do you mean by "restart in the cmd.exe" ?
[Corion]: Do you want to launch a script and keep the command prompt/console window open?
[Corion]: Do you want to wait for a key press before closing the window?
[LanX]: I want the command line in the history
[tye]: -Mouse
[Corion]: Option a) would mean launching cmd.exe /k c:\path\to\ batchfile- launching-perl- script.cmd. Option b) would be to add pause as the last line of said batch file.

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (12)
As of 2017-03-27 15:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should Pluto Get Its Planethood Back?



    Results (320 votes). Check out past polls.