A rover logs n floor-depth readings while crossing a canyon, in travel order. A basin profile is a subsequence of readings (not necessarily adjacent), in travel order, whose depths strictly decrease down to a single lowest reading and then strictly increase. A purely strictly-decreasing subsequence counts as a basin profile (its low point is the last reading), and so does a purely strictly-increasing one (its low point is the first reading). A single reading is a basin profile of length 1. Report the maximum number of readings in a basin profile.
Line 1: an integer n.
Line 2: n space-separated integers, the depths in travel order.
A single integer: the length of the longest valley subsequence.
Example 1
Input
7 7 4 5 1 3 6 2
Expected
5
Explanation
The basin profile 7, 4, 1, 3, 6 strictly falls to the low point 1 then strictly rises, using 5 readings, the most possible here.
Example 2
Input
5 9 7 5 3 1
Expected
5
Explanation
The depths only fall, which is a valid basin profile (low point at the end) using all 5 readings.
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 →