LeetCode 1131. Maximum of Absolute Value Expression Solution in Java, C++, Python & More | Explanation + Code

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

Solutions

Solution 1: Mathematics + Enumeration

Let's denote x_i = arr1[i], y_i = arr2[i]. Since the size relationship between i and j does not affect the value of the expression, we can assume i \ge j. Then the expression can be transformed into:

| x_i - x_j | + | y_i - y_j | + i - j = max \begin{cases} (x_i + y_i) - (x_j + y_j) \ (x_i - y_i) - (x_j - y_j) \ (-x_i + y_i) - (-x_j + y_j) \ (-x_i - y_i) - (-x_j - y_j) \end{cases} + i - j\ = max \begin{cases} (x_i + y_i + i) - (x_j + y_j + j) \ (x_i - y_i + i) - (x_j - y_j + j) \ (-x_i + y_i + i) - (-x_j + y_j + j) \ (-x_i - y_i + i) - (-x_j - y_j + j) \end{cases}

Therefore, we just need to find the maximum value mx and the minimum value mi of a × x_i + b × y_i + i, where a, b ∈ {-1, 1}. The answer is the maximum value among all mx - mi.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Similar problems:

• 1330. Reverse Subarray To Maximize Array Value

PythonJavaC++GoTypeScript

class Solution: def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int: dirs = (1, -1, -1, 1, 1) ans = -inf for a, b in pairwise(dirs): mx, mi = -inf, inf for i, (x, y) in enumerate(zip(arr1, arr2)): mx = max(mx, a * x + b * y + i) mi = min(mi, a * x + b * y + i) ans = max(ans, mx - mi) return ans(code-box)

class Solution { public int maxAbsValExpr(int[] arr1, int[] arr2) { int[] dirs = {1, -1, -1, 1, 1}; final int inf = 1 << 30; int ans = -inf; int n = arr1.length; for (int k = 0; k < 4; ++k) { int a = dirs[k], b = dirs[k + 1]; int mx = -inf, mi = inf; for (int i = 0; i < n; ++i) { mx = Math.max(mx, a * arr1[i] + b * arr2[i] + i); mi = Math.min(mi, a * arr1[i] + b * arr2[i] + i); ans = Math.max(ans, mx - mi); } } return ans; } }(code-box)

class Solution { public: int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) { int dirs[5] = {1, -1, -1, 1, 1}; const int inf = 1 << 30; int ans = -inf; int n = arr1.size(); for (int k = 0; k < 4; ++k) { int a = dirs[k], b = dirs[k + 1]; int mx = -inf, mi = inf; for (int i = 0; i < n; ++i) { mx = max(mx, a * arr1[i] + b * arr2[i] + i); mi = min(mi, a * arr1[i] + b * arr2[i] + i); ans = max(ans, mx - mi); } } return ans; } };(code-box)

func maxAbsValExpr(arr1 []int, arr2 []int) int { dirs := [5]int{1, -1, -1, 1, 1} const inf = 1 << 30 ans := -inf for k := 0; k < 4; k++ { a, b := dirs[k], dirs[k+1] mx, mi := -inf, inf for i, x := range arr1 { y := arr2[i] mx = max(mx, a*x+b*y+i) mi = min(mi, a*x+b*y+i) ans = max(ans, mx-mi) } } return ans }(code-box)

function maxAbsValExpr(arr1: number[], arr2: number[]): number { const dirs = [1, -1, -1, 1, 1]; const inf = 1 << 30; let ans = -inf; for (let k = 0; k < 4; ++k) { const [a, b] = [dirs[k], dirs[k + 1]]; let mx = -inf; let mi = inf; for (let i = 0; i < arr1.length; ++i) { const [x, y] = [arr1[i], arr2[i]]; mx = Math.max(mx, a * x + b * y + i); mi = Math.min(mi, a * x + b * y + i); ans = Math.max(ans, mx - mi); } } return ans; }(code-box)