Maximum of Absolute Value Expression LeetCode Problem

 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

Deriving the Four Cases

We consider all possible combinations of signs for the expression:

(arr1[i]−arr1[j])+(arr2[i]−arr2[j])+(i−j)

To handle absolute values, we expand this expression into four possible cases:

Case 1: arr1[i]>arr1[j] & arr2[i]>arr2[j]

(arr1[i]+arr2[i]+i)−(arr1[j]+arr2[j]+j)

Case 2:arr1[i]>arr1[j] & arr2[i]<arr2[j]

(arr1[i]-arr2[i]+i)−(arr1[j]-arr2[j]+j)

Case 3::arr1[i]<arr1[j] & arr2[j]>arr2[j]

(arr2[j]- arr1[i]+i)−(arr2[j]- arr1[j]+j)

Case 4:arr1[i]<arr1[j] & arr2[i]<arr2[j]

(i-arr1[i]−arr2[i])−(j-arr1[j]−arr2[j])

Both arr2 and i contribute negatively.

Why These Four Cases?

Since |X - Y| means X - Y or Y - X, we account for all positive and negative variations.

Instead of brute-force checking all pairs (i, j), we realize that maximizing each expression is equivalent to:

max(expression)−min(expression)

This allows us to optimize our approach.

Final Algorithm

Compute four transformed arrays based on the four cases above.

For each transformed array:

Track minimum and maximum values.

Compute max - min.

Return the maximum value among the four cases.

class Solution {

    public int maxAbsValExpr(int[] arr1, int[] arr2) {

       

        int n=arr1.length;

        int max1=Integer.MIN_VALUE,min1=Integer.MAX_VALUE;

        int max2=Integer.MIN_VALUE,min2=Integer.MAX_VALUE;

        int max3=Integer.MIN_VALUE,min3=Integer.MAX_VALUE;

        int max4=Integer.MIN_VALUE,min4=Integer.MAX_VALUE;

      for(int i=0;i<n;i++)

        {

      max1=Math.max(max1,arr1[i] + arr2[i] + i);

      min1=Math.min(min1,arr1[i] + arr2[i] + i);

  max2=Math.max(max2,arr1[i] - arr2[i] + i);

      min2=Math.min(min2,arr1[i] - arr2[i] + i);

  max3=Math.max(max3,arr2[i] - arr1[i] + i);

      min3=Math.min(min3,arr2[i] - arr1[i] + i);

  max4=Math.max(max4,i-arr1[i]-arr2[i]);

      min4=Math.min(min4,i-arr1[i]-arr2[i]);

        }

  return Math.max(

            Math.max(max1 - min1, max2 - min2),

            Math.max(max3 - min3, max4 - min4)

        );

    }

}