Is it possible to solve this problem in less than n^2 time without using additional space?
Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &amp;= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &amp;=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-i)) \\ &amp;=
\max \left[ \max_{i,j} (a_i+i) + (a_j-j), \max_{i,j} (a_j+j) + (a_i-i) \right] \\ &amp;\stackrel{(*)}=
\max_{i,j} (a_i+i) + (a_j-j) \\ &amp;=
\max_i (a_i + i) + \max_j (a_j - j).
\end{align*}
$$
The tricky step is $(*)$. The final expression can be computed in linear time and constant space.