| [reply] [d/l] |

*
*
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.
| [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] |