Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
We don't bite newbies here... much
 
PerlMonks  

Re: Puzzle: Longest Increasing Sequence

by TedPride (Priest)
on Apr 16, 2006 at 22:02 UTC ( #543709=note: print w/ replies, xml ) Need Help??


in reply to Puzzle: Longest Increasing Sequence

It was a homework problem assigned to my dad by his Advanced Algorithms instructor (5000-level course), but the instructor only required an O(n^2) algorithm. I, on the other hand, was sure there was SOME way to do it in O(n lg n), so I lay there thinking about the problem for several nights (what does this say about me?) and finally figured out how to do it in a relatively efficient manner. Basically, you store the 1-sequence, 2-sequence, 3-sequence, etc. with the lowest last element. The last elements are therefore arranged in order from the 1-sequence to the x-sequence, since a longer sequence has a larger smallest end item. So for all items in the original array (n), you do a find in the sequence array for the largest item that is smaller than or equal to the item (lg s, where s is the maximum sequence length found so far, or lg n for the worst-case input), link your current item to that sequence and assign it to the sequence one level up, for a total of O(n lg n) time.

So, with an input of 3,5,2,7,12,1...

3: No items to compare to, so put in position 1:
3

5: Larger than 3, so added to the sequence in position 1 and moved to position 2:
3 | 3,5

2: No items smaller, so replaces the squence in position 1:
2 | 3,5

7: Larger than 5, so added to sequence in position 2 and put in position 3:
2 | 3,5 | 3,5,7

12: Added and put in position 4:
2 | 3,5 | 3,5,7 | 3,5,7,12

1: All items larger, so put in position 1:
1 | 3,5 | 3,5,7 | 3,5,7,12

The longest sequence is 3,5,7,12. Now, you might say that since you have to move each sequence up one as you go along, it doesn't matter that it takes only lg n time to find the proper sequence, since it could theoretically take n time to move the sequence with worst-case input. HOWEVER, if you use nodes and links rather than moving the entire sequence, each move only takes constant time, so you succeed in your objective of O(n lg n) or less time, and the most storage space you'll need is n nodes and n sequence storage.

The main issues to think about are:

How do you find the largest key smaller than (or equal to, if allowing non-unique keys) a certain key in a sorted array in O(lg n) time?

How do you keep track of which nodes are linked to and which are no longer needed? I know Perl automatically deallocates structures that are no longer linked to, but if you were programming this in something like C++, you'd need to keep track.

If you can solve these two problems, the basic algorithm itself is quite easy.


Comment on Re: Puzzle: Longest Increasing Sequence
Re^2: Puzzle: Longest Increasing Sequence
by Anonymous Monk on Nov 06, 2011 at 02:28 UTC
    This algorithm will not give us a O(nlogn) running time, because you are copying one of the subsequences on each step. So, it will give you O(n^2). To have O(nlogn) you should do binary search through the last elements of each subsequence and insert it respectively...

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (16)
As of 2014-04-17 18:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (453 votes), past polls