A reservoir gauge logs n water-level readings over a season, in chronological order. A stable stretch is any subsequence of readings (not necessarily consecutive) taken in chronological order whose values never go down — that is, each chosen reading is greater than or equal to the previously chosen one (a non-decreasing subsequence). Report the greatest number of readings a stable stretch can contain.
Line 1: an integer n.
Line 2: n space-separated integers, the readings in chronological order.
A single integer: the length of the longest non-decreasing subsequence.
Example 1
Input
7 3 3 1 4 4 2 5
Expected
5
Explanation
One longest non-decreasing stretch is 3, 3, 4, 4, 5 using 5 readings; equal readings may sit next to each other in the stretch.
Example 2
Input
4 9 7 5 3
Expected
1
Explanation
Each reading is strictly smaller than the one before, so no stretch of two readings is non-decreasing; the best is a single reading.
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 →