The Widest Ramp
A ramp is a pair of indices i < j with a[i] <= a[j]. Print the largest j - i over
all ramps, or 0 if there is none.
6 0 8 2 1 5 -> 4 i = 1 (value 0), j = 5 (value 5)
5 4 3 2 1 -> 0 no pair rises
The comparison is <=, so equal values form a ramp. 1 1 answers 1 and 3 3 3
answers 2. A solution using strict < answers 0 on both, and that is the single most
common mistake here.
## Why every left endpoint is not worth considering
Index i can be discarded as a left endpoint if some earlier index holds a value that
is at most a[i], because that earlier index is a better start: it pairs with every
j that i pairs with, and it is further left.
So the only useful left endpoints are the positions where the running minimum strictly decreases. Collect them left to right, and their VALUES are strictly decreasing by construction.
6 0 8 2 1 5 -> candidate starts at indices 0 and 1, values 6 and 0
## Matching them from the right
Now walk j from the right end leftwards. The candidate list has strictly decreasing
values, so its LAST entry is the smallest. While that last entry's value is at most
a[j], it forms a ramp with j, and since we are sweeping j downwards this j is
the furthest right partner that entry will ever see. Record the width and discard the
entry.
Each candidate is pushed once and discarded once, so the whole thing is O(n) after the
first pass.
The subtle part is why discarding is safe. Once an entry has been matched with the
current j, any later j in the sweep is SMALLER, so it could only give a narrower
ramp. Nothing is lost.
## The alternative worth knowing
Sorting the indices by value, breaking ties by index, and then sweeping while tracking
the smallest index seen gives the same answer in O(n log n) and is easier to get right
under pressure. Both are acceptable; the linear one is the better story.
## Boundaries
A single element has no pair, so the answer is 0. 2 1 also answers 0, and 1 2 3 4
answers 3. Widths are at most n - 1 and fit comfortably in 32 bits.