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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.