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:
(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.9 7 5 3 1 x
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.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^3: Puzzle: Longest Increasing Sequence
by kaif (Friar) on Apr 16, 2006 at 17:10 UTC | |
Re^3: Puzzle: Longest Increasing Sequence
by gaal (Parson) on Apr 17, 2006 at 05:13 UTC |
In Section
Seekers of Perl Wisdom