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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.