难度: Medium
给你两个长度相等的整数数组，返回下面表达式的最大值：
|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运行时间: 55 ms
内存: 27.2 MB
class Solution:
def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
A, B, C, D = [], [], [], []
for i in range(len(arr1)):
A.append(arr1[i]+arr2[i]+i)
B.append(arr1[i]-arr2[i]+i)
C.append(arr1[i]-arr2[i]-i)
D.append(arr1[i]+arr2[i]-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)
本题解采用了数学变换的思路。首先，将原表达式的绝对值拆解为四种情况：(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 和 arr2 的长度相等，可以遍历数组，将对应的表达式值存入四个数组 A, B, C, D 中。最后，分别计算这四个数组的最大值和最小值之差，取四者中的最大值作为结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
A, B, C, D = [], [], [], []
for i in range(len(arr1)):
A.append(arr1[i] + arr2[i] + i) # 对应表达式的第一种情况
B.append(arr1[i] - arr2[i] + i) # 对应表达式的第二种情况
C.append(arr1[i] - arr2[i] - i) # 对应表达式的第三种情况
D.append(arr1[i] + arr2[i] - 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) # 返回四种情况中的最大值
通过对绝对值运算的数学性质分析，绝对值表达式 |a - b| 可以表示为两种情况：a - b 和 b - a。在本题中，由于涉及两个数组和索引的绝对值差，表达式可展开为 |(arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)| 等四种形式。这四种形式分别对应绝对值差的正负两种情况，确保涵盖了所有可能的绝对值组合。
原数组arr1和arr2的元素加上索引i产生了不同的线性表达式，这些表达式并非直接从原数组导出。计算A, B, C, D数组的最大值与最小值之差是为了找到在每种情况下可能达到的最大绝对值差。直接从原数组中计算无法直接得到这些特定线性组合的最大值差，因此需要先转换成A, B, C, D四种形式后，再求各自的最大值与最小值之差。
该方法在计算最大值和最小值之差时是精确的，因为它基于数学变换准确地反映了所有可能的情况。然而，这种方法的计算量随数组长度的增加而线性增加，因为需要对每个数组进行一次完整的遍历来确定最大值和最小值。在极大数据量的情况下，这可能导致时间消耗增大，但不会影响结果的准确性。
将表达式拆分为(arr1[i] + arr2[i] + i)和其他三种形式基于考虑所有可能的正负组合。这种拆分方法是为了确保每个变量(arr1[i], arr2[i], i)在表达式中以加和减的形式出现，从而涵盖所有可能的差的绝对值。虽然理论上可以有其他的拆分方式，比如将所有的组合系数变化（例如2arr1[i] - arr2[i] + 3i等），但这并不是必要的，因为基本的四种形式已经覆盖了所有情形。