634. The Longest Mountain Inside the Array
A MOUNTAIN is a run of consecutive values that rises strictly to a peak and then falls strictly, with at least one step on each side. So a mountain has at least three values and the peak is not at either of its ends.
Print the length of the longest mountain anywhere in the array, or 0 if there is none.
2 1 4 7 3 2 5 -> 5 the run 1 4 7 3 2
2 2 2 -> 0
1 2 3 -> 0 it never comes down
## The change from problem 616
Problem 616 asks whether the WHOLE array is a mountain. This asks for the longest mountain INSIDE it, so the array may contain several, separated by flat stretches or by the wrong direction.
The same climb-then-descend idea drives both, but it now runs repeatedly and each run has to know where it started.
## Three pointers, all moving forward
i = 0
while i + 1 < n:
while i + 1 < n and a[i] >= a[i+1]: i += 1 skip what is not rising
up = i the foot of this mountain
while i + 1 < n and a[i] < a[i+1]: i += 1 climb
peak = i
if peak == up: continue no rise, so no mountain
while i + 1 < n and a[i] > a[i+1]: i += 1 descend
if i > peak: best = max(best, i - up + 1)
up, peak and i all move only forward, and every value is passed a constant number of
times, so the whole thing is one linear pass.
## Why the next search resumes at the end of the descent
After a mountain ends, i sits at the foot of the descent. That position CAN be the foot of
the next mountain, so the loop continues from there rather than skipping past it.
Restarting from i + 1 instead loses any mountain that begins exactly where the previous one
ended, which is the most common bug here.
## Why both strictness checks matter
A flat step is neither a rise nor a fall, so it ends a mountain and begins a fresh search.
2 3 3 2 answers 0: the rise stops at the first 3, and the descent from the second 3 has no
rise before it.
That input is the one to trace, because it looks like a mountain and is not.
## The failed-climb case
If the climb moved nothing, peak == up, and there is no mountain starting here. The
continue sends the loop back to the skip phase, which then advances past this position. That
is what keeps the loop from spinning forever on a descending run.
## Boundaries
Fewer than three values answers 0. A single mountain filling the array answers n.
5 4 3 2 1 2 3 answers 0: it falls and then rises, which is a valley, not a mountain.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the length of the longest mountain, or 0 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.