Maximum Absolute Difference

You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

For example,

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

So, we return 5.

思路:

四种情况:
   |A[i] - A[j]| + |i - j|
= A[i] - A[j] + j - i                  A[i] > A[j] && i < j
= (A[i] - i) - (A[j] - j)

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

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

= A[j] - A[i] + i - j                  A[i] < A[i] && i > j
= (-A[i] + i) - (-A[j] + j)

因为f (i, j) = f(j, i)，我们只需要考虑i < j或者i > j中的一种情况即可，这里我们考虑i < j。
所以我们实际上要得到的是所有 (A[i] - i) - (A[j] - j) 和 (-A[i] - i) - (-A[j] - j)的最大值。

进一步，我们需要找到

所以我们可以用四个变量来记录这四个值，最后找到最大的差。

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public int maxArr(ArrayList<Integer> A) {
        int max1, max2 = Integer.MIN_VALUE;
        int min1, min2 = Integer.MAX_VALUE;
        for (int i = 0; i < A.size(); i ++) {
           max1 = Math.max(max1, A.get(i) - i);
           max2 = Math.max(max2, -A.get(i) - i);
           min1 = Math.min(min1, A.get(i) - i);
           min2 = Math.min(min2, -A.get(i) - i);
        }
        return Math.max(Math.max(max1 - min1), Math.max(max2 - min2));
    }
}