Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 5 / b / 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 byFor example, an implementation on an indexed sequence can use: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 $\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 distinct value is a different specification.