O(n) solution, explanation and proof


#1

For any two numbers x, y, if x >= y then |x -y| = x -y and if x < y then |x - y| = y - x.
Given, f(i,j) = |A[i] - A[j]| + |i - j|
Now, there can be 4 cases:
Case 1: If i >= j and A[i] >= A[j], then f(i,j) = (A[i] + i) - (A[j] + j)
Case 2: If i>=j and A[i] < A[j], then f(i,j) = (A[j] - j) - (A[i] - i)
Case 3: If i<j and A[i] >= A[j], then f(i,j) = (A[i] - i) - (A[j] - j)
Case 4: If i<j and A[i] < A[j], then f(i,j) = (A[j] + j) - (A[i] + i)

If we combine Case 1 and Case 4, and similarly combine Case 2 and Case 3, then the problem is as good as solving for finiding two numbers in an array with maximum difference. For example, in Case 1, imagine all numbers are written in a new array B, such that B[i] = A[i] + i. It is very clear that solving for the best answer in Case 1 and Case 4 is as good as finding the minimum and maximum values in array B and taking their difference. Similarly, we need to do for Case 2 and Case 3.

So the final answer is:
max(max(A[i] + i) - min(A[i] + i), max(A[i] - i) - min(A[i] - i)).

Note: in the above line A[i] + i, refers to the array which is created after it’s index added to it. The index starts from 1 here.

Note: max - min done over any array will always be positive (think about it!!), so the above solution will always respect absolute value constrain on f(i,j).

Since finding minimum and maximum values in an array can be done in O(n), so the overall complexity is O(n).