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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        

Solutions:
class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		N = len(arr1)
		a = [arr1[i] + arr2[i] + i for i in range(N)]
		b = [arr1[i] + arr2[i] - i for i in range(N)]
		c = [arr1[i] - arr2[i] + i for i in range(N)]
		d = [arr1[i] - arr2[i] - i for i in range(N)]
		return max((max(x) - min(x) for x in (a, b, c, d)))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		(A, B, C, D) = ([], [], [], [])
		for i in range(len(arr1)):
			x = arr1[i] + arr2[i] + i
			y = arr1[i] - arr2[i] - i
			z = arr1[i] + arr2[i] - i
			t = arr1[i] - arr2[i] + i
			A.append(x)
			B.append(y)
			C.append(z)
			D.append(t)
		return max(list([max(x) - min(x) for x in [A, B, C, D]]))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		points = list(zip(arr1, arr2, range(n)))
		funcs = [lambda x, y, i: x + y + i, lambda x, y, i: x - y - i, lambda x, y, i: x - y + i, lambda x, y, i: x + y - i]
		res = 0
		for func in funcs:
			temp = [func(*pt) for pt in points]
			res = max(res, max(temp) - min(temp))
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		max1 = max2 = max3 = max4 = float('-inf')
		min1 = min2 = min3 = min4 = float('inf')
		for i in range(0, len(arr1)):
			tmp1 = arr1[i] - arr2[i] - i
			max1 = max(max1, tmp1)
			min1 = min(min1, tmp1)
			tmp2 = arr1[i] + arr2[i] - i
			max2 = max(max2, tmp2)
			min2 = min(min2, tmp2)
			tmp3 = arr1[i] + arr2[i] + i
			max3 = max(max3, tmp3)
			min3 = min(min3, tmp3)
			tmp4 = arr1[i] - arr2[i] + i
			max4 = max(max4, tmp4)
			min4 = min(min4, tmp4)
		return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		ans = 0
		mn = 10 ** 7
		mx = -10 ** 7
		mn1 = 10 ** 7
		mx1 = -10 ** 7
		mn2 = 10 ** 7
		mx2 = -10 ** 7
		mn3 = 10 ** 7
		mx3 = -10 ** 7
		for j in range(len(arr1)):
			tmp = arr1[j] + arr2[j] + j
			tmp1 = arr1[j] - arr2[j] + j
			tmp2 = -arr1[j] + arr2[j] + j
			tmp3 = -arr1[j] - arr2[j] + j
			mn = min(mn, tmp)
			mx = max(mx, tmp)
			mn1 = min(mn1, tmp1)
			mx1 = max(mx1, tmp1)
			mn2 = min(mn2, tmp2)
			mx2 = max(mx2, tmp2)
			mn3 = min(mn3, tmp3)
			mx3 = max(mx3, tmp3)
		return max(mx - mn, mx1 - mn1, mx2 - mn2, mx3 - mn3)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		min1 = min2 = min3 = min4 = float('inf')
		max1 = max2 = max3 = max4 = float('-inf')
		for i in range(len(arr1)):
			(s, d) = (arr1[i] + arr2[i], arr1[i] - arr2[i])
			(min1, max1) = (min(min1, s + i), max(max1, s + i))
			(min2, max2) = (min(min2, s - i), max(max2, s - i))
			(min3, max3) = (min(min3, d + i), max(max3, d + i))
			(min4, max4) = (min(min4, d - i), max(max4, d - i))
		return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		(x, y, z, w) = ([], [], [], [])
		for i in range(len(arr1)):
			x.append(arr1[i] + arr2[i] + i)
			y.append(arr1[i] + arr2[i] - i)
			z.append(arr1[i] - arr2[i] + i)
			w.append(arr1[i] - arr2[i] - i)
		return max(map(lambda a: max(a) - min(a), (x, y, z, w)))


class Solution:

	def join(self, a: List[int], b: List[int], add=True, ascend=True):
		arr = []
		for i in range(len(a)):
			if add:
				arr.append(a[i] + b[i])
			else:
				arr.append(a[i] - b[i])
			if ascend:
				arr[i] += i
			else:
				arr[i] -= i
		return arr

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		if not len(arr1):
			return 0
		(mins, maxes) = ([], [])
		idx = []
		for (i, arr) in enumerate([self.join(arr1, arr2, add, asc) for (add, asc) in [(True, True), (True, False), (False, True), (False, False)]]):
			mins.append(arr[0])
			maxes.append(arr[0])
			idx.append((0, 0))
			for j in range(1, len(arr)):
				if arr[j] < mins[i]:
					mins[i] = arr[j]
					idx[i] = (j, idx[i][1])
				if arr[j] > maxes[i]:
					maxes[i] = arr[j]
					idx[i] = (idx[i][0], j)
		largest_diff = float('-inf')
		if (arr1[idx[0][0]] > arr1[idx[0][1]]) == (arr2[idx[0][0]] > arr2[idx[0][1]]) and idx[0][0] <= idx[0][1]:
			largest_diff = maxes[0] - mins[0]
		if (arr1[idx[1][0]] > arr1[idx[1][1]]) == (arr2[idx[1][0]] > arr2[idx[1][1]]) and idx[1][0] >= idx[1][1]:
			largest_diff = max(largest_diff, maxes[1] - mins[1])
		if (arr1[idx[2][0]] > arr1[idx[2][1]]) != (arr2[idx[2][0]] > arr2[idx[2][1]]) and idx[2][0] <= idx[2][1]:
			largest_diff = max(largest_diff, maxes[2] - mins[2])
		if (arr1[idx[3][0]] > arr1[idx[3][1]]) != (arr2[idx[3][0]] > arr2[idx[3][1]]) and idx[3][0] >= idx[3][1]:
			largest_diff = max(largest_diff, maxes[3] - mins[3])
		return largest_diff


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		arrA = [0] * len(arr1)
		arrC = [0] * len(arr1)
		arrD = [0] * len(arr1)
		arrB = [0] * len(arr1)
		for i in range(len(arr1)):
			arrA[i] = arr1[i] + arr2[i] + i
			arrB[i] = -arr1[i] + arr2[i] + i
			arrC[i] = arr1[i] - arr2[i] + i
			arrD[i] = -arr1[i] - arr2[i] + i
		minA = arrA[0]
		minB = arrB[0]
		minC = arrC[0]
		minD = arrD[0]
		res = 0
		for i in range(1, len(arrA)):
			minA = min(minA, arrA[i])
			minB = min(minB, arrB[i])
			minC = min(minC, arrC[i])
			minD = min(minD, arrD[i])
			res = max(res, arrA[i] - minA, arrB[i] - minB, arrC[i] - minC, arrD[i] - minD)
		return res
		dic1A = {}
		dic2A = {}
		dic1A = {}
		dic2A = {}
		dic2 = {}


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		min1 = min2 = min3 = min4 = float('inf')
		max1 = max2 = max3 = max4 = float('-inf')
		for (i, [n1, n2]) in enumerate(zip(arr1, arr2)):
			(min1, max1) = (min(min1, n1 + n2 + i), max(max1, n1 + n2 + i))
			(min2, max2) = (min(min2, n1 + n2 - i), max(max2, n1 + n2 - i))
			(min3, max3) = (min(min3, n1 - n2 + i), max(max3, n1 - n2 + i))
			(min4, max4) = (min(min4, n1 - n2 - i), max(max4, n1 - n2 - i))
		return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		res = 0
		for (p, q) in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
			smallest = p * arr1[0] + q * arr2[0]
			for i in range(n):
				cur = p * arr1[i] + q * arr2[i] + i
				res = max(cur - smallest, res)
				smallest = min(smallest, cur)
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		vector = [(1, 1), (-1, 1), (1, -1), (-1, -1)]
		res = 0
		sm = float('inf')
		for vec in vector:
			(p, q) = vec
			sm = float('inf')
			for i in range(len(arr1)):
				cur = p * arr1[i] + q * arr2[i] + i
				res = max(res, cur - sm)
				sm = min(cur, sm)
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		a = [arr1[i] + arr2[i] - i for i in range(n)]
		mn = 10 ** 20
		ans = 0
		for i in a[::-1]:
			ans = max(ans, i - mn)
			mn = min(mn, i)
		a = [arr1[i] - arr2[i] - i for i in range(n)]
		mn = 10 ** 20
		for i in a[::-1]:
			ans = max(ans, i - mn)
			mn = min(mn, i)
		a = [arr1[i] - arr2[i] + i for i in range(n)]
		mn = 10 ** 20
		for i in a:
			ans = max(ans, i - mn)
			mn = min(mn, i)
		a = [arr1[i] + arr2[i] + i for i in range(n)]
		mn = 10 ** 20
		for i in a:
			ans = max(ans, i - mn)
			mn = min(mn, i)
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		D = {}
		(a1, a2, a3, a4) = (-2 ** 31, -2 ** 31, -2 ** 31, -2 ** 31)
		(b1, b2, b3, b4) = (2 ** 31, 2 ** 31, 2 ** 31, 2 ** 31)
		for i in range(len(arr1)):
			t = arr1[i] + arr2[i] + i
			a1 = max(a1, t)
			b1 = min(b1, t)
			t = arr1[i] + arr2[i] - i
			a2 = max(a2, t)
			b2 = min(b2, t)
			t = arr1[i] - arr2[i] - i
			a3 = max(a3, t)
			b3 = min(b3, t)
			t = arr1[i] - arr2[i] + i
			a4 = max(a4, t)
			b4 = min(b4, t)
		return max(a1 - b1, a2 - b2, a3 - b3, a4 - b4)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		minmin = []
		minmax = []
		maxmin = []
		maxmax = []
		res = 0
		for (i, (v1, v2)) in enumerate(zip(arr1, arr2)):
			if not minmin or minmin[0] - v1 + minmin[1] - v2 + minmin[2] - i > 0:
				minmin = [v1, v2, i]
			if not minmax or minmax[0] - v1 + v2 - minmax[1] + minmax[2] - i > 0:
				minmax = [v1, v2, i]
			if not maxmin or v1 - maxmin[0] + maxmin[1] - v2 + maxmin[2] - i > 0:
				maxmin = [v1, v2, i]
			if not maxmax or v1 - maxmax[0] + v2 - maxmax[1] + maxmax[2] - i > 0:
				maxmax = [v1, v2, i]
			res = max(res, v1 - minmin[0] + v2 - minmin[1] + i - minmin[2])
			res = max(res, v1 - minmax[0] + minmax[1] - v2 + i - minmax[2])
			res = max(res, maxmin[0] - v1 + v2 - maxmin[1] + i - maxmin[2])
			res = max(res, maxmax[0] - v1 + maxmax[1] - v2 + i - maxmax[2])
		return res


class Solution:

	def calc(self, a, b):
		c = [ai + bi for (ai, bi) in zip(a, b)]
		m = 10 ** 18
		res = 0
		for i in range(len(c)):
			m = min(m, c[i] + i)
			res = max(res, c[i] + i - m)
		return res

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		arr1_ = [-arr1_i for arr1_i in arr1]
		arr2_ = [-arr2_i for arr2_i in arr2]
		return max(self.calc(arr1, arr2), self.calc(arr1, arr2_), self.calc(arr1_, arr2), self.calc(arr1_, arr2_))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		max1 = max2 = max3 = max4 = -math.inf
		min1 = min2 = min3 = min4 = math.inf
		for i in range(len(arr1)):
			x = arr1[i]
			y = arr2[i]
			max1 = max(max1, x + y - i)
			min1 = min(min1, x + y - i)
			max2 = max(max2, x - y - i)
			min2 = min(min2, x - y - i)
			max3 = max(max3, -x + y - i)
			min3 = min(min3, -x + y - i)
			max4 = max(max4, -x - y - i)
			min4 = min(min4, -x - y - i)
		return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:

		def expr(sign1, sign2, i):
			return sign1 * arr1[i] + sign2 * arr2[i] + i

		def diff(sign1, sign2):
			max_ = max((expr(sign1, sign2, i) for i in range(len(arr1))))
			min_ = min((expr(sign1, sign2, i) for i in range(len(arr1))))
			return max_ - min_
		return max((diff(sign1, sign2) for (sign1, sign2) in [(1, 1), (1, -1), (-1, 1), (-1, -1)]))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		(res, n) = (0, len(arr1))
		for (x, y) in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
			mini = x * arr1[0] + y * arr2[0]
			for i in range(n):
				temp = x * arr1[i] + y * arr2[i] + i
				res = max(res, temp - mini)
				mini = min(mini, temp)
		return res


class Solution:

	def maxAbsValExpr(self, arr1, arr2) -> int:
		res = 0
		length = len(arr1)
		for (p, q) in [(1, 1), (-1, -1), (1, -1), (-1, 1)]:
			min_v = p * arr1[0] + q * arr2[0] + 0
			for i in range(1, length):
				v = p * arr1[i] + q * arr2[i] + i
				res = max(res, v - min_v)
				min_v = min(v, min_v)
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		ans = 0
		n = len(arr1)
		for (x, y) in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
			smallest = x * arr1[0] + y * arr2[0] + 0
			for i in range(n):
				cur = x * arr1[i] + y * arr2[i] + i
				ans = max(ans, cur - smallest)
				smallest = min(smallest, cur)
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		(x, y) = (arr1, arr2)
		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)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		maxsize = 2147483647
		min1 = maxsize
		min2 = maxsize
		max1 = -maxsize - 1
		max2 = -maxsize - 1
		min3 = maxsize
		min4 = maxsize
		max3 = -maxsize - 1
		max4 = -maxsize - 1
		for i in range(len(arr1)):
			min1 = min(min1, arr1[i] + arr2[i] + i)
			max1 = max(max1, arr1[i] + arr2[i] + i)
			min2 = min(min2, arr1[i] + arr2[i] - i)
			max2 = max(max2, arr1[i] + arr2[i] - i)
			min3 = min(min3, arr1[i] - arr2[i] + i)
			max3 = max(max3, arr1[i] - arr2[i] + i)
			min4 = min(min4, arr1[i] - arr2[i] - i)
			max4 = max(max4, arr1[i] - arr2[i] - i)
		result = max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)
		return result


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		mx = 0
		for a in [1, -1]:
			for b in [1, -1]:
				sm = a * arr1[0] + b * arr2[0] + 0
				for i in range(1, len(arr1)):
					v = a * arr1[i] + b * arr2[i] + i
					mx = max(mx, v - sm)
					sm = min(sm, v)
		return mx


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		points = list(zip(arr1, arr2, range(n)))
		funcs = [lambda x, y, z: x + y + z, lambda x, y, z: -x + y + z, lambda x, y, z: x - y + z, lambda x, y, z: -x - y + z]
		ans = 0
		for func in funcs:
			mapped = [func(*p) for p in points]
			ans = max(ans, max(mapped) - min(mapped))
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		ans = 0
		for x in (1, -1):
			for y in (1, -1):
				minn = arr1[0] * x + arr2[0] * y
				for i in range(len(arr1)):
					curr = arr1[i] * x + arr2[i] * y + i
					minn = min(minn, curr)
					ans = max(ans, curr - minn)
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		f1 = lambda i: arr1[i] + arr2[i] + i
		f2 = lambda i: -arr1[i] + arr2[i] + i
		f3 = lambda i: arr1[i] - arr2[i] + i
		f4 = lambda i: -arr1[i] - arr2[i] + i
		res = 0
		for f in [f1, f2, f3, f4]:
			low = float('inf')
			high = -float('inf')
			for i in range(len(arr1)):
				low = min(low, f(i))
				high = max(high, f(i))
			res = max(res, high - low)
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		maxVal = 0
		cases = [(1, 1, 1), (1, 1, -1), (1, -1, 1), (1, -1, -1), (-1, 1, 1), (-1, 1, -1), (-1, -1, -1)]
		for case in cases:
			(a, b, c) = case
			if c == 1:
				minVal = a * arr1[0] + b * arr2[0] + 0
				for i in range(1, len(arr1)):
					candidate = a * arr1[i] + b * arr2[i] + c * i
					maxVal = max(maxVal, candidate - minVal)
					minVal = min(minVal, candidate)
			else:
				minVal = a * arr1[-1] + b * arr2[-1] + c * (len(arr1) - 1)
				for i in range(len(arr1) - 2, -1, -1):
					candidate = a * arr1[i] + b * arr2[i] + c * i
					maxVal = max(maxVal, candidate - minVal)
					minVal = min(minVal, candidate)
		return maxVal


class Solution:

	def helper(self, sign1, sign2, arr1, arr2):
		(m1, m2) = (-10 ** 7, 10 ** 7)
		for i in range(len(arr1)):
			t = sign1 * arr1[i] + sign2 * arr2[i] + i
			m1 = max(m1, t)
			m2 = min(m2, t)
		return m1 - m2

	def maxAbsValExpr(self, arr1, arr2):
		res = 0
		res = max(res, self.helper(1, 1, arr1, arr2))
		res = max(res, self.helper(-1, 1, arr1, arr2))
		res = max(res, self.helper(1, -1, arr1, arr2))
		res = max(res, self.helper(-1, -1, arr1, arr2))
		return res


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		for i in range(n):
			(arr1[i], arr2[i]) = (arr1[i] + arr2[i], arr1[i] - arr2[i])
		arr11 = [x + i for (i, x) in enumerate(arr1)]
		arr12 = [x - i for (i, x) in enumerate(arr1)]
		arr21 = [x + i for (i, x) in enumerate(arr2)]
		arr22 = [x - i for (i, x) in enumerate(arr2)]
		return max((max(a) - min(a) for a in [arr11, arr12, arr21, arr22]))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)

		def get_max(arr):
			max_val = 0
			heap = []
			for (idx, val) in enumerate(arr):
				if heap:
					(min_val, min_idx) = heap[0]
					abs_max = val - min_val + idx - min_idx
					if abs_max > max_val:
						max_val = abs_max
				heapq.heappush(heap, (val, idx))
			return max_val
		max_abs = 0
		for first in [-1, 1]:
			for second in [-1, 1]:
				arr = []
				for i in range(n):
					arr.append(first * arr1[i] + second * arr2[i])
				max_abs = max(get_max(arr), max_abs)
		return max_abs


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		ans = float('-inf')
		maxx = [float('-inf')] * 4
		minn = [float('inf')] * 4
		for i in range(n):
			maxx[0] = max(maxx[0], arr1[i] + arr2[i] + i)
			minn[0] = min(minn[0], arr1[i] + arr2[i] + i)
			ans = max(ans, maxx[0] - minn[0])
			maxx[1] = max(maxx[1], arr1[i] + arr2[i] - i)
			minn[1] = min(minn[1], arr1[i] + arr2[i] - i)
			ans = max(ans, maxx[1] - minn[1])
			maxx[2] = max(maxx[2], arr1[i] - arr2[i] + i)
			minn[2] = min(minn[2], arr1[i] - arr2[i] + i)
			ans = max(ans, maxx[2] - minn[2])
			maxx[3] = max(maxx[3], arr1[i] - arr2[i] - i)
			minn[3] = min(minn[3], arr1[i] - arr2[i] - i)
			ans = max(ans, maxx[3] - minn[3])
		return ans


class Solution:

	def maxAbsValExpr(self, A: List[int], B: List[int]) -> int:
		n = len(A)
		max1 = max2 = max3 = max4 = -10 ** 6 - 1
		min1 = min2 = min3 = min4 = 10 ** 6 + 1
		for i in range(n):
			temp = A[i] - B[i] - i
			min1 = min(min1, temp)
			max1 = max(max1, temp)
			temp = A[i] + B[i] - i
			min2 = min(min2, temp)
			max2 = max(max2, temp)
			temp = A[i] + B[i] + i
			min3 = min(min3, temp)
			max3 = max(max3, temp)
			temp = A[i] - B[i] + i
			min4 = min(min4, temp)
			max4 = max(max4, temp)
		ans = max(max4 - min4, max3 - min3, max2 - min2, max1 - min1)
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		ans = 0
		for (p, q) in [(-1, -1), (1, -1), (-1, 1), (1, 1)]:
			min_v = max_v = p * arr1[0] + q * arr2[0]
			for i in range(1, len(arr1)):
				v = p * arr1[i] + q * arr2[i] + i
				min_v = min(min_v, v)
				max_v = max(max_v, v)
			ans = max(ans, max_v - min_v)
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		maxVal = 0
		cases = [(1, 1, 1), (1, 1, -1), (1, -1, 1), (1, -1, -1), (-1, 1, 1), (-1, 1, -1), (-1, -1, -1)]
		for case in cases:
			(a, b, c) = case
			(minimum, maximum) = (float('inf'), float('-inf'))
			for i in range(0, len(arr1)):
				minimum = min(minimum, a * arr1[i] + b * arr2[i] + c * i)
				maximum = max(maximum, a * arr1[i] + b * arr2[i] + c * i)
			maxVal = max(maxVal, maximum - minimum)
		return maxVal


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		maxMax = (arr1[0] + arr2[0], 0)
		minMin = (-arr1[0] - arr2[0], 0)
		minMax = (-arr1[0] + arr2[0], 0)
		maxMin = (arr1[0] - arr2[0], 0)
		table = [maxMax, minMin, minMax, maxMin]
		n = len(arr1)
		ans = 0
		for i in range(1, n):
			for k in range(4):
				(_, j) = table[k]
				ans = max(ans, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + i - j)
				if k == 0:
					newSum = arr1[i] + arr2[i]
				elif k == 1:
					newSum = -arr1[i] - arr2[i]
				elif k == 2:
					newSum = -arr1[i] + arr2[i]
				elif k == 3:
					newSum = arr1[i] - arr2[i]
				if newSum - 1 > table[k][0]:
					table[k] = (newSum, i)
				else:
					table[k] = (table[k][0] + 1, table[k][1])
		return ans


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:

		def getValue(arr):
			return max(arr) - min(arr)
		v1 = [0] * len(arr1)
		v2 = [0] * len(arr1)
		v3 = [0] * len(arr1)
		v4 = [0] * len(arr1)
		for i in range(len(arr1)):
			v1[i] = arr1[i] + arr2[i] + i
			v2[i] = arr1[i] + arr2[i] - i
			v3[i] = arr1[i] - arr2[i] + i
			v4[i] = arr1[i] - arr2[i] - i
		return max(getValue(v1), getValue(v2), getValue(v3), getValue(v4))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		n = len(arr1)
		ma = [float('-inf')] * 4
		res = [float('-inf')] * 4
		for i in range(n - 1, -1, -1):
			a = [arr1[i] - arr2[i] + i, arr1[i] + arr2[i] + i, -arr1[i] + arr2[i] + i, -arr1[i] - arr2[i] + i]
			for j in range(4):
				res[j] = max(res[j], ma[j] - a[j])
			for j in range(4):
				ma[j] = max(ma[j], a[j])
		return max(res)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		case_1_max = case_2_max = case_3_max = case_4_max = -float('inf')
		case_1_min = case_2_min = case_3_min = case_4_min = float('inf')
		for i in range(len(arr1)):
			case_1_max = max(case_1_max, arr1[i] + arr2[i] - i)
			case_1_min = min(case_1_min, arr1[i] + arr2[i] - i)
			case_2_max = max(case_2_max, arr1[i] - arr2[i] - i)
			case_2_min = min(case_2_min, arr1[i] - arr2[i] - i)
			case_3_max = max(case_3_max, arr2[i] - arr1[i] - i)
			case_3_min = min(case_3_min, arr2[i] - arr1[i] - i)
			case_4_max = max(case_4_max, arr2[i] + arr1[i] + i)
			case_4_min = min(case_4_min, arr2[i] + arr1[i] + i)
		return max(case_1_max - case_1_min, case_2_max - case_2_min, case_3_max - case_3_min, case_4_max - case_4_min)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		ans = -math.inf
		n = len(arr1)
		for a in (-1, 1):
			for b in (-1, 1):
				for c in (-1, 1):
					x = -math.inf
					y = math.inf
					for (i, v) in enumerate(arr1):
						x = max(x, a * i + b * v + c * arr2[i])
						y = min(y, a * i + b * v + c * arr2[i])
					ans = max(ans, x - y)
		return ans


class Solution:

	def maxAbsValExpr(self, a1: List[int], a2: List[int]) -> int:
		s1 = []
		s2 = []
		d1 = []
		d2 = []
		for i in range(len(a1)):
			s1.append(a1[i] + a2[i] + i)
			s2.append(a1[i] + a2[i] - i)
			d1.append(a1[i] - a2[i] + i)
			d2.append(a1[i] - a2[i] - i)
		return max(max(s1) - min(s1), max(s2) - min(s2), max(d1) - min(d1), max(d2) - min(d2))


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		c1 = [-9999999999999, -9999999999999, -1]
		c2 = [-9999999999999, -9999999999999, -1]
		c3 = [-9999999999999, -9999999999999, -1]
		c4 = [-9999999999999, -9999999999999, -1]
		c5 = [-9999999999999, -9999999999999, -1]
		c6 = [-9999999999999, -9999999999999, -1]
		c7 = [-9999999999999, -9999999999999, -1]
		c8 = [-9999999999999, -9999999999999, -1]
		lim = len(arr1)
		for i in range(0, lim):
			if arr1[i] + arr2[i] + i > c1[0]:
				c1[0] = arr1[i] + arr2[i] + i
				c1[2] = i
			if arr1[i] - arr2[i] + i > c2[0]:
				c2[0] = arr1[i] - arr2[i] + i
				c2[2] = i
			if -arr1[i] - arr2[i] + i > c3[0]:
				c3[0] = -arr1[i] - arr2[i] + i
				c3[2] = i
			if -arr1[i] + arr2[i] + i > c4[0]:
				c4[0] = -arr1[i] + arr2[i] + i
				c4[2] = i
			if arr1[i] + arr2[i] - i > c5[0]:
				c5[0] = arr1[i] + arr2[i] - i
				c5[2] = i
			if arr1[i] - arr2[i] - i > c6[0]:
				c6[0] = arr1[i] - arr2[i] - i
				c6[2] = i
			if -arr1[i] - arr2[i] - i > c7[0]:
				c7[0] = -arr1[i] - arr2[i] - i
				c7[2] = i
			if -arr1[i] + arr2[i] - i > c8[0]:
				c8[0] = -arr1[i] + arr2[i] - i
				c8[2] = i
		for i in range(0, lim):
			if -arr1[i] - arr2[i] - i > c1[1] and i != c1[2]:
				c1[1] = -arr1[i] - arr2[i] - i
			if -arr1[i] + arr2[i] - i > c2[1] and i != c2[2]:
				c2[1] = -arr1[i] + arr2[i] - i
			if arr1[i] + arr2[i] - i > c3[1] and i != c3[2]:
				c3[1] = arr1[i] + arr2[i] - i
			if arr1[i] - arr2[i] - i > c4[1] and i != c4[2]:
				c4[1] = arr1[i] - arr2[i] - i
			if -arr1[i] - arr2[i] + i > c5[1] and i != c5[2]:
				c5[1] = -arr1[i] - arr2[i] + i
			if -arr1[i] + arr2[i] + i > c6[1] and i != c6[2]:
				c6[1] = -arr1[i] + arr2[i] + i
			if arr1[i] + arr2[i] + i > c7[1] and i != c7[2]:
				c7[1] = arr1[i] + arr2[i] + i
			if arr1[i] - arr2[i] + i > c8[1] and i != c8[2]:
				c8[1] = arr1[i] - arr2[i] + i
		v1 = 0
		if -9999999999999 not in c1:
			v1 = c1[0] + c1[1]
		v2 = 0
		if -9999999999999 not in c2:
			v2 = c2[0] + c2[1]
		v3 = 0
		if -9999999999999 not in c3:
			v3 = c3[0] + c3[1]
		v4 = 0
		if -9999999999999 not in c4:
			v4 = c4[0] + c4[1]
		v5 = 0
		if -9999999999999 not in c5:
			v5 = c5[0] + c5[1]
		v6 = 0
		if -9999999999999 not in c6:
			v6 = c6[0] + c6[1]
		v7 = 0
		if -9999999999999 not in c7:
			v7 = c7[0] + c7[1]
		v8 = 0
		if -9999999999999 not in c8:
			v8 = c8[0] + c8[1]
		print((v1, v2, v3, v4, v5, v6, v7, v8))
		return max(v1, v2, v3, v4, v5, v6, v7, v8)


class Solution:

	def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
		if not arr1 or not arr2:
			return 0
		n = len(arr1)
		(l1, l2, l3, l4) = ([], [], [], [])
		for i in range(len(arr1)):
			l1 += [arr1[i] + arr2[i] + i]
			l2 += [arr1[i] - arr2[i] + i]
			l3 += [-arr1[i] + arr2[i] + i]
			l4 += [-arr1[i] - arr2[i] + i]
		res = []
		res += [max(l1) - min(l1)]
		res += [max(l2) - min(l2)]
		res += [max(l3) - min(l3)]
		res += [max(l4) - min(l4)]
		return max(res)