1131. Maximum of Absolute Value Expression

\1131. Maximum of Absolute Value Expression

Medium

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

1. Brute force

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        ans = 0
        for i in range(1, len(arr1)):
            for j in range(len(arr1)-i):
                cur = abs(arr1[j] - arr1[j+i]) + abs(arr2[j] - arr2[j+i]) + i
                ans = max(ans, cur)
        return ans

Time complexity: O(n^2)

Space complexity: O(1)

2. 对于公式的简化形成四种case

   参考

class Solution:
    def maxAbsValExpr(self, x: List[int], y: List[int]) -> int:
        maxCase1 = maxCase2 = maxCase3 = maxCase4 = -float('inf')
        minCase1 = minCase2 = minCase3 = minCase4 = float('inf')
        for i in range(len(x)):
            maxCase1 = max(maxCase1, x[i]+y[i]-i)
            maxCase2 = max(maxCase2, x[i]-y[i]-i)
            maxCase3 = max(maxCase3, -x[i]+y[i]-i)
            maxCase4 = max(maxCase4, -x[i]-y[i]-i)
            minCase1 = min(minCase1, x[i]+y[i]-i)
            minCase2 = min(minCase2, x[i]-y[i]-i)
            minCase3 = min(minCase3, -x[i]+y[i]-i)
            minCase4 = min(minCase4, -x[i]-y[i]-i)
        return max(maxCase1-minCase1, maxCase2-minCase2, maxCase3-minCase3, maxCase4-minCase4)