A survey drone records the elevation at each of n markers along a mountain ridge, in the order it flew over them. A climbing route is any subsequence of markers (they need not be adjacent) whose elevations are read in the recorded order and are strictly increasing. Report the greatest number of markers such a route can contain.
Line 1: an integer n.
Line 2: n space-separated integers, the elevations in recorded order.
A single integer: the length of the longest strictly increasing subsequence.
Example 1
Input
6 3 1 4 1 5 9
Expected
4
Explanation
One longest strictly increasing route is 1, 4, 5, 9 (or 3, 4, 5, 9), using 4 markers, and no route of 5 exists.
Example 2
Input
5 5 4 3 2 1
Expected
1
Explanation
Every later elevation is smaller, so no two markers can both be on an increasing route; the best route is a single marker.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →