Q:

Expectation of maximum of a function whose expectation is concave

An analysis of a data structure yields a property of the form
$\qquad \mathbb{E}[ f(k) ] = H_k + H_{n-k+1} - 1$
for some natural $n$ and all $1 \leq k \leq n$. Note that the $f(k)$ are not independent.
Now I am interested in the quantity
$\qquad \mathbb{E}[\max_{k=1,\dots,n} f(k)]$.
Since $\mathbb{E}[f(k)]$ is concave on $[1,k]$ if continued on the reals and the maximum is "nice", I think it should be possible to apply (the symmetric version of) Jensen's inequality to conclude
$\qquad \mathbb{E}[\max_{k=1,\dots,n} f(k)] \leq \max_{k=1,\dots,n} \mathbb{E}[f(k)] = \mathbb{E}[f(n/2)] = 2H_{n/2} + \frac{1}{n/2 + 1} - 1$,
glossing over odd $n$. 
Does this really hold? If so, how can I make the argument formal? If not, is there any handle on the desired quantity? Right now, I don't know more about the distribution for $f(k)$.
Note that I can expect a logarithmic bound, so we should be able to make a connection.

A:

Jensen's inequality states that, if $\phi$ is a convex function
\begin{equation}
   \phi( \mathbb{E}X) \leq \mathbb{E}\phi(X)
\end{equation}
In your particular case, consider
\begin{equation}
   \begin{aligned}
      \phi_n : x = (x_1,...,x_n) \mapsto \max_{i \in [1, n]} \{x_i\}
   \end{aligned}
\end{equation}
For all $n$, $\phi_n$ is convex since $\forall t \in [0,1]$, $\max \{ tx^1_i + (1-t)x^2_i\}  \leq t \max\{x^1_i\} + (1-t) \max\{x^2_i\} $, therefore (unfortunately)
\begin{equation}
   \max_i \mathbb E X_i \leq \mathbb{E} (\max_i X_i)
\end{equation}

