= Solution
Track the length `r` of the trailing <constant segment of an array>, and the best length `m` anywhere in the processed prefix:
``
i := 1; r := 1; m := 1;
WHILE i < n DO
IF a[i] = a[i-1] THEN r := r+1 ELSE r := 1 END;
IF r > m THEN m := r END;
i := i+1
END;
``
The <loop invariant> is: $1\leq i\leq n$; `r` is the length of the longest constant suffix of $a[0..i)$; and `m` is the length of the longest <constant segment of an array> within $a[0..i)$. Initially all three lengths are one, using $n\geq1$.
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$, so
$$
\boxed{m=\max\{q-p:0\leq p<q\leq n,\ a[p..q)\text{ is constant}\},\qquad T(n)=\Theta(n).}
$$
The <auxiliary space> is $O(1)$, and $n=1$ correctly returns one without entering the loop.
Back to article page
