Maximum Absolute Difference


#1

Can anyone elaborate how -

f(i, j) = |A[i] - A[j]| + |i - j| can be written in 4 ways (Since we are looking at max value, we don’t even care if the value becomes negative as long as we are also covering the max value in some way).

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

Note that case 1 and 4 are equivalent and so are case 2 and 3.


#2

you can check my sol for your query
int Solution::maxArr(vector &A) {
int len=A.size();
int arr[len]={0};
int arr1[len]={0};
for(int i=0;i<len;i++)
{
arr[i]=A[i]+i;
arr1[i]=A[i]-i;
}
int ma=INT_MIN;
int mi=INT_MAX;
for(int i=0;i<len;i++)
{
if(arr[i]>ma)
ma=arr[i];
if(arr[i]<mi)
mi=arr[i];
}
int sum=abs(ma-mi);
ma=INT_MIN;
mi=INT_MAX;
for(int i=0;i<len;i++)
{
if(arr1[i]>ma)
ma=arr1[i];
if(arr1[i]<mi)
mi=arr1[i];
}
int sum1=abs(ma-mi);
int result=max(sum,sum1);
return result;
}


#3

I am not getting why you have done like this… can you explain your approach?


#4

As mentioned above, below ones are equivalent to two cases

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

They are (A[i] + i) - (A[j] + j) or -(A[i] + i) + (A[j] + j) and -(A[i] - i) + (A[j] - j) or (A[i] - i) - (A[j] - j)
I will take first one i.e., (A[i] + i) - (A[j] + j) and explain
In this, When you maximise (A[i] + i) and minimise (A[j] + j) then automatically their difference will be maximum. And as (A[i] + i) - (A[j] + j) and -(A[i] + i) + (A[j] + j) are equivalent you can do for case only.
Same applies to -(A[i] - i) + (A[j] - j) and (A[i] - i) - (A[j] - j) .
Atlast you will check which one of two cases’s maximum is actual maximum and then return.