给你两个长度相等的整数数组,返回下面表达式的最大值:
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
其中下标 i,j 满足 0 <= i, j < arr1.length。
来源:力扣(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)
因为存在四组两两等价的展开,所以可以优化为四个表达式:
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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。