Maximum of Absolute Value Expression

Problem Description

Given two arrays of integers with equal lengths, return the maximum value of:

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

where the maximum is taken over all 0 <= i, j < arr1.length.

Example 1:

Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
Output: 13
Example 2:

Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
Output: 20

Constraints:

2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

Intuition

Take |x[i] - x[j]| + |y[i] - y[j]| as Manhattan distance of two points. x is the coordinate of points on the x-axis, y is the coordinate of points on the y-axis.

Playground

Code

Java

public int maxAbsValExpr(int[] x, int[] y) {
    int res = 0, n = x.length, P[] = {-1,1};
    for (int p : P) {
        for (int q : P) {
            int smallest = p * x[0] + q * y[0] + 0;
            for (int i = 1; i < n; ++i) {
                int cur = p * x[i] + q * y[i] + i;
                res = Math.max(res, cur - smallest);
                smallest = Math.min(smallest, cur);
            }
        }
    }
    return res;
}

Python

# Trick: Keep track of depth and update it via the traversal length. Make sure you stack left first then right to ensure properly visiting right first.
def maxAbsValExpr(self, x, y):
  res, n = 0, len(x)
  for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
      smallest = p * x[0] + q * y[0] + 0
      for i in xrange(n):
          cur = p * x[i] + q * y[i] + i
          res = max(res, cur - smallest)
          smallest = min(smallest, cur)
  return res

C++

//C++
int maxAbsValExpr(vector<int>& x, vector<int>& y) {
    int res = 0, n = x.size(), smallest, cur;
    for (int p : {1, -1}) {
        for (int q : {1, -1}) {
            smallest = p * x[0] + q * y[0] + 0;
            for (int i = 1; i < n; ++i) {
                cur = p * x[i] + q * y[i] + i;
                res = max(res, cur - smallest);
                smallest = min(smallest, cur);
            }
        }
    }
    return res;
}

Source: https://leetcode.com/problems/maximum-of-absolute-value-expression/