3
$\begingroup$

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?

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

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.

$\endgroup$
2
$\begingroup$

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} $$

$\endgroup$
  • 1
    $\begingroup$ 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}}$. ... $\endgroup$ – j_random_hacker Jan 3 at 16:30
  • 1
    $\begingroup$ ... 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}$. $\endgroup$ – j_random_hacker Jan 3 at 16:30
  • $\begingroup$ Hopefully the new version of my answer is less confusing. $\endgroup$ – Yuval Filmus Jan 3 at 22:17

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .