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 \times x_i + b \times y_i + i$, where $a, b \in {-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:
1
2
3
4
5
6
7
8
9
10
11
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
}
|
