Maximum of Absolute Value Expression

medium math absolute value manhattan distance

Problem

Given two integer arrays arr1 and arr2 of equal length, return the maximum value of |arr1[i] − arr1[j]| + |arr2[i] − arr2[j]| + |i − j| over all pairs of indices 0 ≤ i, j < arr1.length.

Inputarr1 = [1, 2, 3, 4], arr2 = [-1, 4, 5, 6]

Output13

Taking i = 0, j = 3: |1 − 4| + |-1 − 6| + |0 − 3| = 3 + 7 + 3 = 13.

arr1 (comma-separated)

arr2 (comma-separated)

def max_abs_val_expr(arr1, arr2):
    ans = 0
    for s1 in (1, -1):
        for s2 in (1, -1):
            best = -float('inf')
            worst = float('inf')
            for i in range(len(arr1)):
                val = s1 * arr1[i] + s2 * arr2[i] + i
                best = max(best, val)
                worst = min(worst, val)
            ans = max(ans, best - worst)
    return ans

function maxAbsValExpr(arr1, arr2) {
  let ans = 0;
  for (const s1 of [1, -1]) {
    for (const s2 of [1, -1]) {
      let best = -Infinity, worst = Infinity;
      for (let i = 0; i < arr1.length; i++) {
        const val = s1 * arr1[i] + s2 * arr2[i] + i;
        best = Math.max(best, val);
        worst = Math.min(worst, val);
      }
      ans = Math.max(ans, best - worst);
    }
  }
  return ans;
}

class Solution {
    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int ans = 0;
        int[] signs = { 1, -1 };
        for (int s1 : signs) {
            for (int s2 : signs) {
                int best = Integer.MIN_VALUE, worst = Integer.MAX_VALUE;
                for (int i = 0; i < arr1.length; i++) {
                    int val = s1 * arr1[i] + s2 * arr2[i] + i;
                    best = Math.max(best, val);
                    worst = Math.min(worst, val);
                }
                ans = Math.max(ans, best - worst);
            }
        }
        return ans;
    }
}

int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
    int ans = 0;
    for (int s1 : {1, -1}) {
        for (int s2 : {1, -1}) {
            int best = INT_MIN, worst = INT_MAX;
            for (int i = 0; i < (int)arr1.size(); i++) {
                int val = s1 * arr1[i] + s2 * arr2[i] + i;
                best = max(best, val);
                worst = min(worst, val);
            }
            ans = max(ans, best - worst);
        }
    }
    return ans;
}

Explanation

Checking every pair (i, j) would be slow. The clever trick is to get rid of the absolute-value signs by trying every way they could open up, which turns the problem into a fast single pass.

Each |x - y| is either x - y or y - x. With three absolute terms there are really just four sign combinations that matter, captured by the signs s1 and s2 (each either +1 or -1) applied to arr1 and arr2.

For a fixed pair of signs, every index i produces a single value val = s1*arr1[i] + s2*arr2[i] + i. The biggest the whole expression can be for that combo is simply the largest such value minus the smallest one, so we track best and worst in one loop.

We do this for all four sign combos and keep the overall maximum in ans. Because a max minus a min always corresponds to a valid pair of indices, this never overshoots the true answer.

Example: with arr1 = [1,2,3,4], arr2 = [-1,4,5,6], the combo +arr1 +arr2 + i gives values whose range turns out to be 13, which is the answer.

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