Maximum absolute difference in an array

Question

I came across this algorithm question. I was able to implement a O(n^2) solution. Is there a better way of doing this in O(n) time?

Question:

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.

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.

My Answer:

public class Solution {     public int maxArr(ArrayList<Integer> A) {         int maxSum = 0;          for(int i=1; i<=A.size()-1; i++){             for(int j=i+1; j<=A.size(); j++){                 int tempSum = sum(A.get(i-1), A.get(j-1), i, j);                  if(tempSum > maxSum) {                     maxSum = tempSum;                 }             }         }          return maxSum;     }      public int sum(int Ai, int Aj, int i, int j) {         return Math.abs(Ai-Aj) + Math.abs(i-j);     } } 

Also in my solution the inner loop runs from i + 1 to N, so the worst case is N-1 for that loop. Is my overall solution still O(n^2)?

Answer 1

Yes, your solution is still O(N^2) as (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2.

I'll show how to solve a more general problem in linear time: give a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).

1. Let's find the following points: max(x[i] + y[i]), max(-x[i] + y[i]), max(-y[i] + x[i]) and max(-x[i] - y[i]) among all i.

2. Let's compute the distance between every point in the list and the four points chosen during the previous step and pick the largest one. This algorithm clearly works in linear time as it considers 4 * N pairs of points. I claim that it's correct.

3. Why? Let's fix a point (x[k], y[k]) and try to find the farthest one from it. Consider an arbitrary point (x[i], y[i]). Let's expand the absolute value of differences between their coordinates. Let's assume that it's x[i] + x[k] + y[i] + y[k] = (x[k] + y[k]) + x[i] + y[i]. The first term is a constant. If x[i] + y[i] is not maximum among all i, (x[i], y[i]) cannot be the farthest. The three other cases (depending on the sign of x[i] and y[i] in the expansion) are handled in the same manner.