Question is very interesting.. both methods brute force and exact solution


#1

int Solution::maxArr(vector &A) {

/* int res = INT_MIN;

for(int i = 0;i<A.size();i++)
{
    for(int j = i + 1;j<A.size();j++)
    {
        int temp = abs(A[i] - A[j]) + abs(i - j);
        
        if(temp > res)
        res = temp;
    }
}

return res;*/


// here we have to apply the basic properties of modulus operation..

int max1 = INT_MIN;
int min1 = INT_MAX;
int max2 = INT_MIN;
int min2 = INT_MAX;


// here we have to consider all the four cases as given by modulus function..

// case 1 : i > j
    // 1.a :  A[i] > A[j] --->   this will give (A[i] + i) - (A[j] + j)   ....
    // 1.b :  A[i] < A[j] --->   this will give -(A[i] - i) + (A[j] - j)  ....
    
// case 2 : i < j 
    // 2.a : A[i] > A[j] --->   this will give (A[i] - i) - (A[j] - j)   ....
    // 2.b : A[i] < A[j] --->   this will give -(A[i] + i) + (A[j] + j)  ....
    
    
for(int i = 0;i<A.size();i++)
{
    max1 = max(max1 , A[i] + i);
    min1 = min(min1 , A[i] + i);
    max2 = max(max2 , A[i] - i);
    min2 = min(min2 , A[i] - i);
}

// now we have taken all of our extreme cases..
// now we have to take our answer..

int res = INT_MIN;

for(int i = 0;i<A.size();i++)
{
    res = max(res , abs(max1 - (A[i] + i)));
    res = max(res , abs(min1 - (A[i] + i)));
    res = max(res , abs(max2 - (A[i] - i)));
    res = max(res , abs(min2 - (A[i] - i)));
}

return res;

}