Leecode #1131 绝对值表达式的最大值

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

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

解题思路

1. 三维曼哈顿距离

​ 先讲二维曼哈顿距离：

x1-x2

+

y1-y2

。如何求一组点之间最大的曼哈顿距离呢？

​ 首先我们要定义坐标系上4个角，然后对于一个角，求各个点到这个角的距离，并得到最大距离的差值。4个最大距离差值的最大值即最大的曼哈顿距离，原理来自https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/339968/JavaC%2B%2BPython-Maximum-Manhattan-Distance

​

arr1[i] - arr1[j]

+

arr2[i] - arr2[j]

+

i - j

，我们可以将arr1视为x坐标，arr2视为y坐标，index视为z坐标。扩展到三维的曼哈顿距离我们需要定义8个角，然后就可以求出点之间最大的三维曼哈顿距离啦~代码如下

def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        # arr1 作为x轴， arr2作为y轴， index作为z轴
        rlt = -1
        max_length = 10**6
        corner = [
            [-max_length, -max_length, -max_length],
            [-max_length, -max_length, max_length],
            [-max_length, max_length, -max_length],
            [-max_length, max_length, max_length],
            [max_length, -max_length, -max_length],
            [max_length, -max_length, max_length],
            [max_length, max_length, -max_length],
            [max_length, max_length, max_length],
        ]
        for i in range(8):
            mmax = -1
            mmin = 10**7
            for j in range(len(arr1)):
                dis = self.distance([arr1[j], arr2[j], j], corner[i])
                mmax = max(mmax, dis)
                mmin = min(mmin, dis)
            rlt = max(rlt, mmax - mmin)
        return rlt

    def distance(self,corner, index):
        return sum([abs(corner[i]-index[i]) for i in range(3)])
    

下面介绍一种复杂度更低的方法

2. 分情况讨论

首先看|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]|这部分和的最大值，很明显有四种情况

1. 当 arr1[i] > arr1[j], arr2[i] > arr2[j]
		f = arr1[i] - arr1[j] + arr2[i] - arr2[j] 
			= (arr1[i]+arr2[i]) - (arr1[j]+arr2[j])
			
2. 当 arr1[i] < arr1[j], arr2[i] > arr2[j]
		f = -arr1[i] + arr1[j] + arr2[i] - arr2[j] 
			= (-arr1[i]+arr2[i]) - (-arr1[j]+arr2[j])

3. 当 arr1[i] > arr1[j], arr2[i] < arr2[j]
		arr1[i] - arr1[j] - arr2[i] + arr2[j] 
			= (arr1[i]-arr2[i]) - (arr1[j]-arr2[j])
			
4. 当 arr1[i] < arr1[j], arr2[i] < arr2[j]
		-arr1[i] + arr1[j] - arr2[i] + arr2[j] 
			= -(arr1[i]+arr2[i]) + (arr1[j]+arr2[j])

因为i和j可以互换，所以14和23等同，于是我们可以提取出2种情况X1[i] = arr1[i]+arr2[i], X2[i] = arr1[i]-arr2[i]

目标函数f = max((max(X1)-min(X1)), (max(X2)-min(X2))

现在处理|i-j|只要分为i-j和j-i的情况加在后面就好啦，代码如下

def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        A, B, C, D= [], [], [], []
        for i in range(len(arr1)):
            x, y = arr1[i], arr2[i]
            A.append(x + y + i)
            B.append(x + y - i)
            C.append(x - y + i)
            D.append(x - y - i)
        a = max(A) - min(A)
        b = max(B) - min(B)
        c = max(C) - min(C)
        d = max(D) - min(D)        
        return max(a, b, c, d)