455. Up Then Down

A subsequence is a MOUNTAIN if it strictly increases to a peak and then strictly decreases. Either side may be empty, so a purely increasing or purely decreasing subsequence counts, and a single element counts as a mountain of length 1.

Print the length of the longest mountain subsequence.

1 11 2 10 4 5 2 1 -> 6 1 2 10 5 2 1 (peak at 10)

The obstacle is that the answer is not built left to right. An element's contribution depends on what comes BEFORE it, for the rising part, and on what comes AFTER it, for the falling part.

So run two passes in opposite directions:

inc[i] longest strictly increasing subsequence ENDING at i dec[i] longest strictly decreasing subsequence STARTING at i

Each is the ordinary problem #452 scan, the second one run from the right.

Then every index is a candidate peak:

answer = max over i of inc[i] + dec[i] - 1

The - 1 is the detail that decides correctness. Index i belongs to both subsequences and would otherwise be counted twice. Omitting it inflates every answer by exactly one, which looks plausible on every input and is always wrong.

Because both sides may be empty, the formula needs no special case for a monotonic input: a purely increasing sequence has dec[i] = 1 at its last element, which contributes nothing extra.

Constraints - `1 ≤ n ≤ 2000` - `-1000000 ≤ value ≤ 1000000`