http://www.perlmonks.org?node_id=543624


in reply to Puzzle: Longest Increasing Sequence

Isn't this O(n)? Scan the list and maintain the tuple (start index, length) for your best candidate so far, as well as for the subsequence you are looking at now. If you are currently looking at your best candidate, keep incremening both length field as long as the sequence is monotonic. Reset the 'current' tuple or install the 'best' tuple as appropriate.
  • Comment on Re: Puzzle: Longest Increasing Sequence

Replies are listed 'Best First'.
Re^2: Puzzle: Longest Increasing Sequence
by BrowserUk (Patriarch) on Apr 16, 2006 at 10:40 UTC

    This works if you are looking for the longest contiguous ascending sequence.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
Re^2: Puzzle: Longest Increasing Sequence
by jdporter (Paladin) on Apr 16, 2006 at 15:42 UTC

    The problem is, you could have as many as i (where i = 1 to n) "best candidates" at any time. Consider — if the list looks like this: 

    9 7 5 3 1 x

    [download]
    (i.e. you've processed all but the last number) you won't know until you look at the last number which of the preceding numbers (if any) are in the solution. x could be 10, or it could be 2, for example.

    So you need to keep all the increasing subsequences seen so far; and that could be as many as n; and that means the algorithm is at least O(n log n).

    We're building the house of the future together.
[reply]
[d/l]
      Well, no, you only need to keep at most one increasing subsequence for each length. In your example, you can forget about the 9, 7, 5, and 3 entirely. Any increasing subsequence beginning with them will be just as long if they begin with the 1 instead.
[reply]
      Yes, as BrowserUk++ points out, I was wrongly assuming contiguous subsequences in the problem statement.
[reply]

In Section Seekers of Perl Wisdom