Pathologically Eclectic Rubbish Lister  
PerlMonks 
Re: Patience Sorting To Find Longest Increasing Subsequenceby TedPride (Priest) 
on May 03, 2006 at 17:34 UTC ( #547221=note: print w/replies, xml )  Need Help?? 
You build an array of sequences..
1sequence Where each nsequence is the nsequence with the smallest possible end item. By the nature of the structure, the end items will always be listed in increasing order  the end item for the 2sequence will always be less than or equal to the end item for the 3sequence. Now, for each new item, just find the sequence with the largest end item that is smaller than or equal to the current item. Link your current item to this sequence and link the slot for the next largest sequence to your current item. Rinse and repeat until all items are processed. For instance, given 3, 5, 2, 1, 7:
3: (3) The only really hard part is coming up with a binary find for the largest item that's smaller than or equal to the current item. I know it's possible, but the exact algorithm eludes me. I'm currently using simplefind() for test purposes  an O(n) algorithm rather than the proper O(lg n). Fixing this will make the entire algorithm O(n lg n). (EDIT: Actually, it's O(n lg s), where s is the longest sequence, but worstcase is s = n) (You may also notice, by the way, that the entire sequence is reconstructed from data stored along the way. It's also possible to store just the the subscript of the end item in each nlength sequence, then do a linear find backwards from that point, recreating the sequence as you go from all the items smaller than or equal to the current part of the sequence.)
In Section
Meditations

