Standard Bar Dynamic Programming · DP on LIS O(n^2) · O(n)
A mountain railway records the elevations of n pylons. A scenic route must climb strictly over a stretch of pylons and then descend strictly over the rest — a mountain shape. The survey team wants the longest such ride measured in pylons visited; a pure climb or a pure descent also counts as scenic.
Input: An array nums of n positive integers (pylon elevations).
Output: Return the length of the longest subsequence that is strictly increasing then strictly decreasing (either flank may be empty).
1 <= n <= 10001 <= nums[i] <= 10^5Input: {"nums":[1,2,1,5,4,2,6,4]}
Output: 5
1, 2, 5, 4, 2 — climb to 5 then fall to 2.
Input: {"nums":[1,2,3,4,5]}
Output: 5
A pure climb qualifies with an empty descent flank.