Return to Revisions

Partial answer: The problem admits an $O(\log n)$ algorithm.

The algorithm $\mathcal A$ works as follows:

1. Query $x = A[n/3]$ and $y = A[2n/3]$.
2. If $x = y$, return $\max \{x, \mathcal A(A[1, n/3]), \mathcal A(A[2n/3, n])\}$
3. If $x < y$, return $\max \{\mathcal A(A[n/3, 2n/3]), \mathcal A(A[2n/3, n])\}$
4. If $x > y$, return $\max \{\mathcal A(A[1, n/3]), \mathcal A(A[n/3, 2n/3])\}$

($A[p, q]$ denotes the sub-array of $A$ starting at index $p$ and ending at index $q$.)

It should be easy to see that $\mathcal A$ works correctly. The running time $T(n)$ of $\mathcal A$ is given by $T(n) = O(1) + 2 \cdot T(n / 3)$, which solves to $T(n) = O(\log n)$.