Maximum of | arr[ i ] - arr[ j ] | + | i - j | . HARD AMAZON OA QUESTION

https://practice.geeksforgeeks.org/problems/a-difference-of-values-and-indexes0302/1

ASKED IN AMAZON OA

Given an unsorted array arr[ ] of size n, you need to find the maximum difference of absolute values of elements and indexes, i.e., for i <= j, calculate maximum of | arr[ i ] - arr[ j ] | + | i - j |.

Example 1:

Input :
n = 3
arr[ ] = {1, 3, -1}
Output: 5
Explanation:
Maximum difference comes from indexes
1, 2 i.e | 3 - (-1) | + | 1 - 2 | = 5

Example 2:

Input :
n = 4
arr[ ] = {5, 9, 2, 6}
Output:  8
Explanation:
Maximum difference comes from indexes
1, 2 i.e | 9 - 2 | + | 1 - 2 | = 8


----------------------------------------------------------------------------------------------------------------------------------

class Solution{
  public:
    int maxDistance(int A[], int n) {
        /*
        Let us walk through all possible cases in | A[i]-A[j] | + | i-j | ->
            1. A[i]>A[j] , i>j
               A[i]-A[j] --- positive
               i-j       --- positive
               (A[i]+i)-(A[j]+j)  ------------------- Eqn 1

            2. A[i]<A[j] , i<j
               A[i]-A[j] --- negative
               i-j       --- negative
               -((A[i]+i)-(A[j]+j))  ------------------- Eqn 2

            3. A[i]<A[j] , i>j
               A[i]-A[j] --- negative
               i-j       --- positive
               (A[j]-j)-(A[i]-i)  ------------------- Eqn 3

            4. A[i]>A[j] , i<j
               A[i]-A[j] --- positive
               i-j       --- negative
               -((A[j]-j)-(A[i]-i)) ------------------- Eqn 4

            Eqn 3 and 4 are the same only difference in sign
            Eqn 1 and 2 are the same only difference in sign,
            So we consider these two sets of equations
        */

        int mx1=INT_MIN;
        int mn1=INT_MAX;

        int mx2=INT_MIN;
        int mn2=INT_MAX;

        // mx1, mn1 represents the largest and smallest arr[i]+i
        // mx2, mn2 represents the largest and smallest arr[i]-i

        for(int i=0;i<n;i++){
            mx1=max(mx1,A[i]+i);
            mn1=min(mn1,A[i]+i);

            mx2=max(mx2,A[i]-i);
            mn2=min(mn2,A[i]-i);
        }
        int res=0;

        /* First set of equations are-
            1. (A[i]+i)-(A[j]+j)
            2. -((A[i]+i)-(A[j]+j));

            The best solution can only be achieved when ---
                res=max(res,mx1-mn1);
                res=max(res,-(mn1-mx1));

            BUT BOTH OF THESE TWO res are SAME on REARRANGING so we use only one
        */
        res=max(res,mx1-mn1);

        /* Second set of equations are-
            1. (A[j]-j)-(A[i]-i)
            2. -((A[j]-j)-(A[i]-i));

            The best solution can only be achieved when ---
                res=max(res,mx2-mn2);
                res=max(res,-(mn2-mx2));

            BUT BOTH OF THESE TWO res are SAME on REARRANGING so we use only one
        */
        res=max(res,mx2-mn2);
        return res;
    }
};