绝对值表达式的最大值

给你两个长度相等的整数数组，返回下面表达式的最大值：

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

其中下标 i，j 满足 0 <= i, j < arr1.length。

 

示例 1：

输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
输出：13
示例 2：

输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
输出：20
 

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-of-absolute-value-expression
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
 
 =  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)
 =  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)
 =  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)
 =  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)
 = -(arr1[i] + arr2[i] + i) + (arr1[j] + arr2[j] + j)
 = -(arr1[i] + arr2[i] - i) + (arr1[j] + arr2[j] - j)
 = -(arr1[i] - arr2[i] + i) + (arr1[j] - arr2[j] + j)
 = -(arr1[i] - arr2[i] - i) + (arr1[j] - arr2[j] - j)
 
因为存在四组两两等价的展开,i 和 j 是可以互换的,所以可以优化为四个表达式：
A = arr1[i] + arr2[i] + i
B = arr1[i] + arr2[i] - i
C = arr1[i] - arr2[i] + i
D = arr1[i] - arr2[i] - i

max( |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|)
= max(max(A) - min(A),
      max(B) - min(B),
      max(C) - min(C),
      max(D) - min(D))

作者：JiayangWu
链接：https://leetcode-cn.com/problems/maximum-of-absolute-value-expression/solution/python-jie-fa-bao-li-shu-xue-by-jiayangwu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int n = arr1.length;

        // 展开表达式，根据正负号合并部分表达式，然后求某个表达式的最大值
        int minA = Integer.MAX_VALUE, maxA = Integer.MIN_VALUE,
                minB =  Integer.MAX_VALUE, maxB = Integer.MIN_VALUE,
                minC =  Integer.MAX_VALUE, maxC = Integer.MIN_VALUE,
                minD =  Integer.MAX_VALUE, maxD = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++)
        {
            minA = Math.min(minA, arr1[i] + arr2[i] + i);
            maxA = Math.max(maxA, arr1[i] + arr2[i] + i);

            minB =  Math.min(minB, arr1[i] - arr2[i] + i);
            maxB = Math.max(maxB, arr1[i] - arr2[i] + i);

            minC =  Math.min(minC, arr2[i] - arr1[i] + i);
            maxC = Math.max(maxC, arr2[i] - arr1[i] + i);

            minD =  Math.min(minD, -(arr1[i] + arr2[i] - i));
            maxD = Math.max(maxD, -(arr1[i] + arr2[i] - i));
        }

        return Math.max(maxA - minA, Math.max(maxB - minB, Math.max(maxC - minC, maxD - minD)));
    
    }
}

赏

谢谢你请我吃糖果

微信