= Solution
Maintain the two largest entries of each segment, counting repeated values as separate entries. A singleton returns its value and a sentinel $-\infty$ for its missing runner-up. Split a longer segment into two nonempty halves, recursively obtain $(m_L,s_L)$ and $(m_R,s_R)$, and combine them by
$$
(m,s)=\begin{cases}
(m_L,\max(s_L,m_R)),&m_L\ge m_R,\\
(m_R,\max(m_L,s_R)),&m_L<m_R.
\end{cases}
$$
For example, an implementation on an indexed <sequence> can use:
``
top2(lo, hi):
if hi-lo == 1: return (a[lo], -infinity)
mid = (lo+hi)//2
(mL,sL) = top2(lo,mid)
(mR,sR) = top2(mid,hi)
if mL >= mR: return (mL, max(sL,mR))
else: return (mR, max(mL,sR))
``
The result is `top2(0,n)`. The global maximum is one of the two child maxima. Once its side is identified, the global second maximum is either that side's runner-up or the other side's maximum; the displayed formula exhausts these possibilities. This proves the <divide-and-conquer algorithm> by <induction> on segment length. There are $n$ leaves and $n-1$ constant-cost combinations, so its <time complexity> is \b[$\Theta(n)$], with $O(\log n)$ recursive stack space for balanced splits. A `Maybe` value can replace the formal sentinel for a generic ordered element type. If both largest entries are equal, both are returned; a second \i[distinct] value is a different specification.
Back to article page
