原文链接: https://leetcode-cn.com/problems/maximum-of-absolute-value-expression
英文原文
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
Constraints:
2 <= arr1.length == arr2.length <= 40000-10^6 <= arr1[i], arr2[i] <= 10^6
中文题目
给你两个长度相等的整数数组，返回下面表达式的最大值：
|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
通过代码
高赞题解
第一种思路 - 暴力解
分析：
此题乍一看很简单，要求 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|，直接上双重循环的暴力解即可，然而数据规模较大，结果超时。
Python代码实现：
[-Python]class Solution(object): def maxAbsValExpr(self, arr1, arr2): """ :type arr1: List[int] :type arr2: List[int] :rtype: int """ res = 0 for i in range(len(arr1)): for j in range(len(arr2)): res = max(res, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j)) return res
复杂度分析：
时间复杂度：$O(N^2)$
空间复杂度：$O(1)$
第二种思路 - 数学解
分析:
既然暴力解不可行，那么我们就需要思考有没有更好的办法，已知要求 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| 的最大值，我们可以先考虑一下子问题的求解：
子问题 1. 求
|arr1[i] - arr1[j]|的最大值这就比较简单了，可以直观地看出来答案，一个数组
arr1里两个元素差的绝对值的最大值，应该等于max(arr1) - min(arr1)子问题 2. 求
|arr1[i] - arr1[j]| + |i - j|的最大值比上一题复杂了一点，观察并不能得出答案，因此，不妨把表达式的绝对值符号去掉，看看展开后会得到怎样的结果：
abs( arr1[i] - arr1[j]) + abs(i - j) = arr1[i] - arr1[j] + i - j = (arr1[i] + i) - (arr1[j] + j) # 式1 = arr1[i] - arr1[j] - i + j = (arr1[i] - i) - (arr1[j] - j) # 式2 = -arr1[i] + arr1[j] + i - j = -(arr1[i] - i) + (arr1[j] - j) # 式3 = -arr1[i] + arr1[j] - i + j = -(arr1[i] + i) + (arr1[j] + j) # 式4因为
i和j是可以互换的，所以式 $1$ 等价于式 $4$， 式 $2$ 等价于式 $3$，因此可以得到：abs( arr1[i] - arr1[j]) + abs(i - j) = (arr1[i] + i) - (arr1[j] + j) ------式1 = (arr1[i] - i) - (arr1[j] - j) ------式2现在不难发现， 原始表达式的值只取决于两个中间表达式：
中间表达式
A = arr1[i] + i中间表达式
B = arr1[i] - i所以有：
max(abs( arr1[i] - arr1[j]) + abs(i - j) ) = max((arr1[i] + i) - (arr1[j] + j), (arr1[i] - i) - (arr1[j] - j)) = max( max(A) - min(A), max(B) - min(B))因此，不难得到子问题的求解代码如下：
[-Python]class Solution(object): def maxAbsValExpr(self, arr1, arr2): """ :type arr1: List[int] :type arr2: List[int] :rtype: int """ A = [] B = [] for i, x in enumerate(arr1): A.append(x + i) B.append(x - i) return max(max(A) - min(A), max(B) - min(B))
现在已经知道了子问题如何求解，那么本题也可以采用相同的解法，首先把绝对值符号去掉，展开表达式：
|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))Python代码实现:
[-Python]class Solution(object): def maxAbsValExpr(self, arr1, arr2): """ :type arr1: List[int] :type arr2: List[int] :rtype: 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)
复杂度分析:
时间复杂度：$O(N)$
空间复杂度：$O(N)$
优化分析：
其实，并没有必要储存所有的 ·A,B,C,D· 表达式的值，
因为我们需要的仅仅是 ·A,B,C,D· 表达式的最大值和最小值，
因此可以用八个变量替代四个数组，将空间优化到 $O(1)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 3200 | 7005 | 45.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
