Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem:

Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range from 0 to length -1. i and j potentially could be the same.

Upon reasoning, I concluded that it is not possible. Am I wrong?

Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-i)) \\ &=
\max \left[ \max_{i,j} (a_i+i) + (a_j-j), \max_{i,j} (a_j+j) + (a_i-i) \right] \\ &\stackrel{(*)}=
\max_{i,j} (a_i+i) + (a_j-j) \\ &=
\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.

StackExchange Computer Science Q#102310, answer score: 7