Attempting to understand the provided solution

This problem stumped me completely. As such, I spent the next couple of hours attempting to understand the provided solution. This is the result of that. If something is incorrect, feedback would be appreciated.

Our goal is to find integers i and j, where 1 <= i, j <= N, maximizing:

abs(A[i] - A[j]) + abs(i - j)

We can split this maximization task into four cases, corresponding to the two possibilities for the sign of each of the two absolute value expressions.

1: A[i] < A[j], i < j: (A[j] - A[i]) + (j - i)
2: A[i] < A[j], i >= j: (A[j] - A[i]) + (i - j)
3: A[i] >= A[j], i < j: (A[i] - A[j]) + (j - i)
4: A[i] >= A[j], i >= j: (A[i] - A[j]) + (i - j)

Normally, each of these cases would be valid only for those i, j satisfying its respective constraint. However, remembering that our task is maximization, we note that for some arbitrary i, j, the formula for the case whose constraint is met by the chosen i, j happens to also yield the maximum value out of all four possibilities. Thus, we no longer need to worry about choosing the specific case satisfied by a particular choice of i, j during our optimization process. We can instead simply evaluate all four cases over all possible choices of i, j and choose the result with maximum value. That is, our task becomes that of maximizing each of the following, for all 1 <= i, j <= N:

1: (A[j] - A[i]) + (j - i)
2: (A[j] - A[i]) + (i - j)
3: (A[i] - A[j]) + (j - i)
4: (A[i] - A[j]) + (i - j)

And returning the maximum result. At this point, we can note that the first and fourth, as well as the second and third cases are equivalent. So, eliminating the two redundant cases and rewriting the remaining two slightly, we have:

1: (A[j] - A[i]) + (j - i) = (A[j] + j) - (A[i] + i)
2: (A[j] - A[i]) + (i - j) = (A[j] - j) - (A[i] - i)

At which point, the maximum of the first for 1 <= i, j <= N is:

max(A[i] + i) - min(A[i] + i)

And the maximum of the second for 1 <= i, j <= N is:

max(A[i] - i) - min(A[i] - i)

And we simply return the greater of the two.

we note that for some arbitrary i, j , the formula for the case whose constraint is met by the chosen i, j happens to also yield the maximum value out of all four possibilities. Thus, we no longer need to worry about choosing the specific case satisfied by a particular choice of i, j during our optimization process.
I didn’t understand this part. why we need not to follow the constraint for maximization.

I do have the same confusion! As what I try my best to understand, we can understand this point from making simple examples:
Eg. We found a pair (i1, j1), which maximizes the formula (A[j] - A[i]) + (j - i). However, the constraint A[i] < A[j], i < j is not met:

( a ) A[i1] < A[j1], i1 >= j1

If so, then we can know, at least, (A[j1] - A[i1]) + (i1 - j1) > (A[j1] - A[i1]) + (i1 - j1), which means the maxium of the formula (A[j] - A[i]) + (i - j) > the maximum of the formula (A[j] - A[i]) + (j - i). So in this case, the wrong result (A[j1] - A[i1]) + (i1 - j1) won’t be finally selected (because at least the formula (A[j] - A[i]) + (i - j) should be selected priorly)

( b ) A[i1] > A[j1], i1 < j1

If so, then we can know, at least, (A[i1] - A[j1]) + (j1 - i1) > (A[j1] - A[i1]) + (j1 - i1), which means the maxium of the formula (A[i] - A[j]) + (j - i) > the maximum of the formula (A[j] - A[i]) + (j - i). So in this case, the wrong result (A[j1] - A[i1]) + (i1 - j1) won’t be finally selected.

( c ) A[i1] > A[j1], i1 > j1

If so, then we can know, at least, (A[i1] - A[j1]) + (i1 - j1) > (A[j1] - A[i1]) + (j1 - i1), which means the maxium of the formula (A[i] - A[j]) + (i - j) > the maximum of the formula (A[j] - A[i]) + (j - i). So in this case, the wrong result (A[j1] - A[i1]) + (i1 - j1) won’t be selected.

Actually, case ( c ) is never possible because if the (i1, j1) is really the maximum of formula (A[i1] - A[j1]) + (i1 - j1) > (A[j1] - A[i1]) + (j1 - i1), then there’s no other pair (i, j) will generate the larger result. But (j1, i1) will obviouly generate the larger result than (i1, j1).

Similar case in (i2, j2), (i3, j3) and (i4, j4).

In summary, for each formula, when the constraint is met, the optimization result of this formula is probably be selected. But when the constraint is not met, the result is guaranteed to not be selected. So, we don’t need to worry about if the constraint can be met when we do the optimization process.

Please correct me if there’s anything wrong or unclear!

Click here to start solving coding interview questions