# 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?

• Do you have any sketch of your reasoning? The problem is to select two indices in $\mathcal o(n^2)$? – Evil Jan 3 at 5:51
• “Not possible” is a big statement. – gnasher729 Jan 4 at 11:59

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.

Something was bothering me about Yuval Filmus's answer so I wrote it down in detail to convince myself that it was right. Perhaps someone else might also find it useful so I'm posting it as an answer.

$$\begin{eqnarray} \max_{i,j} a_i + a_j + |i-j| &=& \max_{i,j} (a_i + a_j + \max(i-j,j-i)) \nonumber \\ &=& \max_i( \max_{j \leq i}(a_i + a_j + i - j), \max_{j \gt i}(a_i + a_j + j - i)) \nonumber \\ &=& \max_i( \max_{j \leq i}(a_i + a_j + i - j), \max_{j \lt i}(a_j + a_i + i - j)) \nonumber \\ &=& \max_i( \max_{j \leq i}(a_i + a_j + i - j), \max_{j \lt i}(a_i + a_j + i - j)) \nonumber \\ &=& \max_i \max_{j \leq i}(a_i + a_j + i - j) \nonumber \\ &=& \max_i( a_i + i + \max_{j \leq i}(a_j - j)) \nonumber \end{eqnarray}$$

Here you need an extra argument to separate the variables : If $$i_{max}$$ is the index where $$\max_i(a_i + i)$$ is reached, and $$j_{max}$$ is where the $$\max_j(a_j - j)$$ is reached, then it follows that $$i_{max} \geq j_{max}$$.

You can then write :

$$\begin{eqnarray} \max_i( a_i + i + \max_{j \leq i}(a_j - j)) &=& \max_i( a_i + i + \max_{j}(a_j - j)) \nonumber \\ &=&\max_i( a_i + i) + \max_{j}(a_j - j) \end{eqnarray}$$

• I like what you're trying to do here, and I'd like to give more detail on "then it follows that $i_{max} \ge j_{max}$": Assume to the contrary that $i_{max} < j_{max}$. Then for all $i > i_{max}$, we have that $a_i + i \le a_{i_{max}} + i_{max}$ by maximality of $i_{max}$. In particular this holds for $i=j_{max}$. Thus $a_{j_{max}} + j_{max} \le a_{i_{max}} + i_{max}$, so $a_{j_{max}} \le a_{i_{max}} + i_{max} - j_{max}$. $i_{max} - j_{max} < 0$ since $i_{max} < j_{max}$ by assumption, so $a_{j_{max}} \le a_{i_{max}} + (i_{max} - j_{max}) < a_{i_{max}}$. ... – j_random_hacker Jan 3 at 16:30
• ... Keeping just the outside parts, we have $a_{j_{max}} < a_{i_{max}}$. Then $a_{j_{max}} < a_{i_{max}} < a_{i_{max}} + (j_{max} - i_{max})$, since the parenthesised expression is positive by assumption. But then subtracting $j_{max}$ from both the outside parts implies $a_{j_{max}} - j_{max} < a_{i_{max}} - i_{max}$, contradicting maximality of $j_{max}$. – j_random_hacker Jan 3 at 16:30
• Hopefully the new version of my answer is less confusing. – Yuval Filmus Jan 3 at 22:17