Array
Math
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:
Python3 Java C++ Go TypeScript
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 ;
}
GitHub