PerlSensitive Sunglasses  
PerlMonks 
Re: Puzzle: Longest Increasing Sequenceby TedPride (Priest) 
on Apr 16, 2006 at 22:02 UTC ( #543709=note: print w/ replies, xml )  Need Help?? 
So, with an input of 3,5,2,7,12,1...
3: No items to compare to, so put in position 1:
5: Larger than 3, so added to the sequence in position 1 and moved to position 2:
2: No items smaller, so replaces the squence in position 1:
7: Larger than 5, so added to sequence in position 2 and put in position 3:
12: Added and put in position 4:
1: All items larger, so put in position 1: 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 worstcase 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 nonunique 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.
In Section
Seekers of Perl Wisdom

