C++ O(n) Solution with Simple Explanation


#1

Explanation:
Here we have f(i, j) = |A[i] - A[j]| + |i-j|
The 4 possible cases here are:

Case 1:
i>j and A[i] > A[j]:
f(i,j) can be rewritten as: (A[i]+i) - (A[j]+j)

Case 2:
i<j and A[i] < A[j]:
f(i,j) can be rewritten as: (A[j]+j) - (A[i]+i)

Case 3:
i<j and A[i] > A[j]:
f(i,j) can be rewritten as: (A[i] - i) - (A[j] - j)

Case 4:
i>j and A[i] < A[j]:
f(i,j) can be rewritten as: (A[j] - j) - (A[i] - i)

The 4 noticeable things to compute here are:
1. Maximum1 = max(A[i]+i)
2. Minimum1 = min(A[i]+i)
3. Maximum2 = max(A[i]-i)
4. Minimum2 = min(A[i]-i)

The function needs to return max(Maximum1 - Minimum1, Maximum2 - Minimum2)

Code:
int Solution::maxArr(vector &A) {

int maxAiplusi=INT_MIN, maxAiminusi=INT_MIN,minAiplusi=INT_MAX, minAiminusi=INT_MAX;

for(int i=0;i<A.size();i++){
    maxAiplusi = max(maxAiplusi, A[i]+i);
    maxAiminusi= max(maxAiminusi,A[i]-i);
    minAiplusi = min(minAiplusi,A[i]+i);
    minAiminusi= min(minAiminusi,A[i]-i);
}

int opt1,opt2;
opt1 = maxAiplusi - minAiplusi;
opt2 = maxAiminusi-minAiminusi;

return max(opt1,opt2);

}


#2

amazin approach taken