Prove the time complexity of this algorithm of finding longest subarray with maximum value in the middle
Let an array $a[1],\ldots,a[n]$ be given. For an index $i$, let $\ell(i)$ be the largest $\ell$ such that $\{i-\ell,\ldots,i+\ell\} \subseteq \{1,\ldots,n\}$ and $a[i]$ is larger than all elements $a[i-\ell],\ldots,a[i-1],a[i+1],a[i+\ell]$. It is not difficult to see that the running time of the algorithm on the array is $\Theta(n + \sum_{i=1}^n \ell(i))$.

This prompts the following definition:


  Given $n$, the quantity $M(n)$ is the maximum of $\sum_{i=1}^n \ell(i)$ over all arrays of length $n$.


Let $a$ be an array for which $M(n)$ is achieved, and let $a[i]$ be an element of maximum value. Then $\ell(i) = \min(i-1,n-i)$. Moreover, since $a[i]$ is not smaller than any other element, we have $\sum_{j=1}^{i-1} \ell(j) \leq M(i-1)$ and $\sum_{j=i+1}^n \ell(j) \leq M(n-i)$. This shows that
$$
M(n) \leq \max_{i=1}^n M(i-1) + M(n-i) + \min(i-1,n-i).
$$
In fact it is not hard to check that equality holds: take the maximum $i$, and combine two arrays attaining $M(i-1)$ and $M(n-i)$ with a larger element in the middle. This gives the recurrence
$$
M(0)=0, \; M(n) = \max_{i=1}^n [M(i-1) + M(n-i) + \min(i-1,n-i)].
$$
This recurrence is A078903. It is intuitively clear that the best choice for $i$ is $\lfloor \frac{n+1}{2} \rfloor$ or $\lceil \frac{n+1}{2} \rceil$.

We can solve the recurrence explicitly: for $0 \leq k &lt; 2^m$, we have
$$
M(2^m+k) = (m-2)2^{m-1}+1+N_2(k),
$$
where $N_2(k)$ is the total number of 1s in the binary expansions of $1,\ldots,k$ (this is A000788). It is known that $N_2(k) = k\log_2 k + O(k)$, and so $M(n) = \Theta(n\log n)$. This asymptotic estimate also follows from the monotonicity of $M(n)$, by considering the cases $k = 0$.

We conclude that the running time of the algorithm is indeed $O(n\log n)$, and moreover this estimate is tight.