Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 2

Track the length r of the trailing constant segment of an array, and the best length m anywhere in the processed prefix:The loop invariant is: $1\le i\le n$; r is the length of the longest constant suffix of $a[\mathrm{0..}i)$; and m is the length of the longest constant segment of an array within $a[\mathrm{0..}i)$. Initially all three lengths are one, using $n\ge 1$.

When the next entry equals its predecessor, the trailing constant segment extends by one; otherwise its new length is one. Every new plateau either was already in the old prefix or ends at the new entry, so taking the larger of the old m and the new r preserves the loop invariant. The loop variant is $n-i$, a nonnegative integer decreased by one. At termination $i=n$, soThe auxiliary space is $O(1)$, and $n=1$ correctly returns one without entering the loop.

Use binary search on an interval with unequal endpoint values. The array need not be sorted:The loop invariant isIt holds initially by the given endpoint inequality, which also implies $n\ge 1$. When $r-l>1$, $l<m<r$. If $b[l]\ne b[m]$, replacing $r$ maintains unequal endpoints. Otherwise $b[m]=b[l]\ne b[r]$, so replacing $l$ maintains them. This does not require monotonicity or even just two possible values.

The positive integer width $r-l$ is a loop variant, reduced to at most its old half rounded up. On exit $r=l+1$, givingThere are at most $\lceil {\log }_{2}n\rceil$ iterations. The additive constant handles $n=1$.