Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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.


In reply to Re: Puzzle: Longest Increasing Sequence by TedPride
in thread Puzzle: Longest Increasing Sequence by TedPride

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others taking refuge in the Monastery: (3)
    As of 2014-10-26 05:22 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      For retirement, I am banking on:










      Results (151 votes), past polls