Maximum absolute difference in an array

We can surely use some math here. Try to Expand the Function you are trying to maximise. F(i,j) = |A[i] - A[j]| + |i - j| Expanding it will give us 4 values of F.

 1. A[i] - A[j] + i - j   equals to [A[i] + i] - [A[j]+j]
 2. -A[i] + A[j] + i - j  equals to [-A[i] + i] - [-A[j]+j]
 3. A[i] - A[j] + j - i   equals to [A[i] - i] - [A[j]-j]
 4. -A[i] + A[j] + j - i  equals to [-A[i] - i] - [-A[j]-j]

Compute the Maximum and Minimum Value of [A[i] + i],[-A[i] + i],[A[i] - i],[-A[i] - i] for all elements in vector/array. call it max1,max2,max3,max4 and min1,min2,min3,min4.

Your Answer is Max((max1-min1),(max2-min2),(max3-min3),(max4-min4)).

Here is the Problem Link if anyone is interested :- Problem Link

Below is my implementation in c++

int Solution::maxArr(vector<int> &A) {
int max1 = INT_MIN,max2 = INT_MIN,max3 = INT_MIN,max4 = INT_MIN,ans = INT_MIN;
int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX,min4 = INT_MAX;
for(int i=0;i<A.size();i++){
    max1 = max(max1,A[i] + i);
    max2 = max(max2,A[i] - i);
    max3 = max(max3,-A[i]+i);
    max4 = max(max4,-A[i]-i);

    min1 = min(min1,A[i] + i);
    min2 = min(min2,A[i] - i);
    min3 = min(min3,-A[i]+i);
    min4 = min(min4,-A[i]-i);

}


    ans = max(ans,max1 - min1);
    ans = max(ans,max2 - min2);
    ans = max(ans,max3 - min3);
    ans = max(ans,max4 - min4);

return ans;

}

O(N) Time Complexity and O(1) Space complexity solution

This question can be solved in O(N) Time and O(1) space complexity by using simple mathematics concepts of absolute operator.

We can deduce this express into 4 different forms after removing the absolute operator and applying specific conditions.

Cases can be A[i]>A[j] or A[i]<=A[j] and simultaneously i>j and i<=j can be the cases so using these conditions we can formulate 4 different expressions which eliminate use of absolute operator.

After that we just need to find the maximum value possible through each expression by iterating on array of numbers only once.

If you still face any difficulties while solving this question then you can refer to the video solution

Video Link:- https://youtu.be/Ov4weYCIipg

Yes, your solution is still O(N^2) as (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

I'll show how to solve a more general problem in linear time: give a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).

1. Let's find the following points: max(x[i] + y[i]), max(-x[i] + y[i]), max(-y[i] + x[i]) and max(-x[i] - y[i]) among all i.

2. Let's compute the distance between every point in the list and the four points chosen during the previous step and pick the largest one. This algorithm clearly works in linear time as it considers 4 * N pairs of points. I claim that it's correct.

3. Why? Let's fix a point (x[k], y[k]) and try to find the farthest one from it. Consider an arbitrary point (x[i], y[i]). Let's expand the absolute value of differences between their coordinates. Let's assume that it's x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]. The first term is a constant. If x[i] + y[i] is not maximum among all i, (x[i], y[i]) cannot be the farthest. The three other cases (depending on the sign of x[i] and y[i] in the expansion) are handled in the same manner.

As described by Kraskevich, I applied the same algorithm. The complexity of the code is O(4*n)+O(4*n), thus making the overall complexity O(n).

Here is the code.

int Solution::maxArr(vector<int> &A) {
int n=A.size(),max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,max4=INT_MIN,ans=INT_MIN;
for(int i=0;i<n;i++){
    max1=max(max1,A[i]+i);
    max2=max(max2,-A[i]+i);
    max3=max(max3,A[i]-i);
    max4=max(max4,-A[i]-i);
}
for(int i=0;i<n;i++){
    ans=max(ans,max1-A[i]-i);
    ans=max(ans,max2+A[i]-i);
    ans=max(ans,max3-A[i]+i);
    ans=max(ans,max4+A[i]+i);
}
return ans;
}