Re: Puzzle: Longest Increasing Sequence

[gaal]

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.

[BrowserUk]

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

[jdporter]

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

[kaif]

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.

[gaal]

Yes, as BrowserUk++ points out, I was wrongly assuming contiguous subsequences in the problem statement.