Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Re^2: Puzzle: Longest Increasing Sequence

by jdporter (Canon)
on Apr 16, 2006 at 15:42 UTC ( #543650=note: print w/ replies, xml ) Need Help??

in reply to Re: Puzzle: Longest Increasing Sequence
in thread Puzzle: Longest Increasing Sequence

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
(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.

Comment on Re^2: Puzzle: Longest Increasing Sequence
Download Code
Re^3: Puzzle: Longest Increasing Sequence
by kaif (Friar) on Apr 16, 2006 at 17:10 UTC
    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.
Re^3: Puzzle: Longest Increasing Sequence
by gaal (Parson) on Apr 17, 2006 at 05:13 UTC
    Yes, as BrowserUk++ points out, I was wrongly assuming contiguous subsequences in the problem statement.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543650]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (16)
As of 2015-04-01 13:58 GMT
Find Nodes?
    Voting Booth?

    Who makes your decisions?

    Results (21 votes), past polls