[leetcode] 1131. Maximum of Absolute Value Expression

[leetcode] 1131. Maximum of Absolute Value Expression

Description

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|最大值，这道题暴力破解ac不了，需要推导，我说一下别人的推导过程：

|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)

因为有绝对值，去掉绝对值后有8种情况，存在四组两两等价的展开，所以可以优化为四个表达式：

A = arr1[i] + arr2[i] + iB = arr1[i] + arr2[i] - iC = arr1[i] - arr2[i] + iD = arr1[i] - arr2[i] - imax( |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))

如果能够推导出这么简洁的方式那么代码就能写出来了，最后的答案就是每个数组的最大值-最小值的差，取最大。这道题我不会，学习一下，哈哈哈。

代码

class Solution: def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int: n=len(arr2) A=[] B=[] C=[] D=[] for i in range(n): 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) return max(max(A)-min(A),max(B)-min(B),max(C)-min(C),max(D)-min(D))

参考文献

​​Python 解法 （暴力 + 数学）​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。