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

Difficulty: interview

Starter code:

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

Solutions:
# https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/340075/c%2B%2B-beats-100-(both-time-and-memory)-with-algorithm-and-image
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 = [], [], [], []
        # https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/340075/c++-beats-100-(both-time-and-memory)-with-algorithm-and-image 
        # much easier to understand.
        # we need to break the four absolute value and reduce them. We can see there are 8 cases but only 4 cases. We generate 4 arrays and compute max() - min()
        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:
        '''
        |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
        4 cases:
        
        1) arr1[i] > arr1[j] and arr2[i] < arr2[j]
            remove abs
            arr1[i] - arr1[j] + arr2[j] - arr2[i] + j - i
            (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)
            
        2) arr1[i] > arr1[j] and arr2[i] > arr2[j]
            remove abs
            arr1[i] - arr1[j] + arr2[i] - arr2[j] + j - i
            (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)
            
        3) arr1[i] < arr1[j] and arr2[i] < arr2[j]
            remove abs
            arr1[j] - arr1[i] + arr2[j] - arr2[i] + j - i
            (arr1[j] + arr2[j] + j) - (arr1[i] + arr2[i] + i)
            
        4) arr1[i] < arr1[j] and arr2[i] > arr2[j]
            remove abs
            arr1[j] - arr1[i] + arr2[i] - arr2[j] + j - i
            (arr1[j] - arr2[j] + j) - (arr1[i] - arr2[i] + i)
        '''
        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:
        # 1. arr1[i] - arr1[j] + arr2[i] - arr2[j] + i - j => ( arr1[i] + arr2[i] + i) - ( arr1[j] + arr2[j] + j)
        # 2. arr1[i] - arr1[j] + arr2[i] - arr2[j] + j - i => ( arr1[i] + arr2[i] - i) - ( arr1[j] + arr2[j] - j)
        # 3. arr1[i] - arr1[j] + arr2[j] - arr2[i] + i - j => ( arr1[i] - arr2[i] + i) - ( arr1[j] - arr2[j] + j)
        # 4. arr1[i] - arr1[j] + arr2[j] - arr2[i] + j - i => ( arr1[i] - arr2[i] - i) - ( arr1[j] - arr2[j] - j)
        # 5. arr1[j] - arr1[i] + arr2[i] - arr2[j] + i - j => (-arr1[i] + arr2[i] + i) - (-arr1[j] + arr2[j] + j)
        # 6. arr1[j] - arr1[i] + arr2[i] - arr2[j] + j - i => (-arr1[i] + arr2[i] - i) - (-arr1[j] + arr2[j] - j)
        # 7. arr1[j] - arr1[i] + arr2[j] - arr2[i] + i - j => (-arr1[i] - arr2[i] + i) - (-arr1[j] - arr2[j] + j)
        # 8. arr1[j] - arr1[i] + arr2[j] - arr2[i] + j - i => (-arr1[i] - arr2[i] - i) - (-arr1[j] - arr2[j] - j)
        # min1, max1 for arr1[i] + arr2[i] + i
        # min2, max2 for arr1[i] + arr2[i] - i
        # min3, max3 for arr1[i] - arr2[i] + i
        # min4, max4 for arr1[i] - arr2[i] - i
        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:
        #|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
        #j>i
        #=max(arr1[j]-arr1[i]+arr2[j]-arr2[i]+j-i,
        #     arr1[i]-arr1[j]+arr2[j]-arr2[i]+j-i,
        #     arr1[j]-arr1[i]+arr2[i]-arr2[j]+j-i,
        #     arr1[i]-arr1[j]+arr2[i]-arr2[j]+j-i)
        #arrA=arr1+arr2
        #arrB=arr2-arr1
        #arrC=arr1-arr2
        #arrD=-arr1-arr2
        #arr?[j]-arr?[i]+j-i
        #(arr?[j]+j)-(arr?[i]+i)
        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:
        # 1. arr1[i] - arr1[j] + arr2[i] - arr2[j] + i - j => ( arr1[i] + arr2[i] + i) - ( arr1[j] + arr2[j] + j)
        # 2. arr1[i] - arr1[j] + arr2[i] - arr2[j] + j - i => ( arr1[i] + arr2[i] - i) - ( arr1[j] + arr2[j] - j)
        # 3. arr1[i] - arr1[j] + arr2[j] - arr2[i] + i - j => ( arr1[i] - arr2[i] + i) - ( arr1[j] - arr2[j] + j)
        # 4. arr1[i] - arr1[j] + arr2[j] - arr2[i] + j - i => ( arr1[i] - arr2[i] - i) - ( arr1[j] - arr2[j] - j)
        # 5. arr1[j] - arr1[i] + arr2[i] - arr2[j] + i - j => (-arr1[i] + arr2[i] + i) - (-arr1[j] + arr2[j] + j)
        # 6. arr1[j] - arr1[i] + arr2[i] - arr2[j] + j - i => (-arr1[i] + arr2[i] - i) - (-arr1[j] + arr2[j] - j)
        # 7. arr1[j] - arr1[i] + arr2[j] - arr2[i] + i - j => (-arr1[i] - arr2[i] + i) - (-arr1[j] - arr2[j] + j)
        # 8. arr1[j] - arr1[i] + arr2[j] - arr2[i] + j - i => (-arr1[i] - arr2[i] - i) - (-arr1[j] - arr2[j] - j)
        # min1, max1 for arr1[i] + arr2[i] + i
        # min2, max2 for arr1[i] + arr2[i] - i
        # min3, max3 for arr1[i] - arr2[i] + i
        # min4, max4 for arr1[i] - arr2[i] - i
        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:
        a = [arr1[i] + arr2[i] + i for i in range(len(arr1))]
        b = [arr1[i] + arr2[i] - i for i in range(len(arr1))]
        c = [arr1[i] - arr2[i] + i for i in range(len(arr1))]
        d = [arr1[i] - arr2[i] - i for i in range(len(arr1))]
        return max(map(lambda x: max(x) - min(x), (a, b, c, d)))

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:
        res, n = 0, len(arr1)
        for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
            smallest = p * arr1[0] + q * arr2[0] + 0
            for i in range(n):
                cur = p * arr1[i] + q * arr2[i] + i
                res = max(res, cur - smallest)
                smallest = min(smallest, cur)
        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:
        #fix i and test for j
        
        # count arr1 i, arr2 i, ind
        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])
            #print(maxmax[0]-v1+maxmax[1]-v2+i-maxmin[2])
        #print(minmin,minmax,maxmin,maxmax)    
        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_))

#https://t123456ll.github.io/1131.%20Maximum%20of%20Absolute%20Value%20Expression.html

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:
        max1 = max2 = max3 = max4 = float('-inf')
        min1 = min2 = min3 = min4 = float('inf')

        for i in range(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:

        n = len(arr1)
        points = list(zip(arr1, arr2, range(n)))
        # Create 4 functions that can give abs value possibilities based on
        # whether arr1[i] is larger or smaller than arr1[j] and so on.
        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:
        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:
        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)
        #  abs(a1[i]-a1[j])+abs(a2[i]-a2[j])
        # =max(a1i+a2i-a1j-a2j, a1i-a2i-a1j+a2j,
        #      -a1i+a2i+a1j-a2j, -a1i-a2i+a1j+a2j)
        #
        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 = [] # min_val, min_idx
            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:
        x = [arr1[i] + arr2[i] + i for i in range(len(arr1))]
        y = [arr1[i] + arr2[i] - i for i in range(len(arr1))]
        z = [arr1[i] - arr2[i] + i for i in range(len(arr1))]
        w = [arr1[i] - arr2[i] - i for i in range(len(arr1))]
        
        return max(map(lambda a: max(a) - min(a), (x,y,z,w)))

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        
        def get_max(arr):
            max_val = 0
            min_val, min_idx = float('inf'), float('inf')
            for idx, val in enumerate(arr):
                if min_idx < float('inf'):
                    abs_max = val - min_val + idx - min_idx
                    if abs_max > max_val:
                        max_val = abs_max
                if val + idx < min_val + min_idx:
                    min_val, min_idx = 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:
        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  = a*arr1[0] + b*arr2[0] + 0, a*arr1[0] + b*arr2[0] + 0
            for i in range(1, 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)
            # 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 maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        points = list(zip(arr1, arr2, list(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,
        ]
        
        result = 0
        for func in funcs:
            mapped = [func(*p) for p in points]
            result = max(result, max(mapped) - min(mapped))
        
        return result


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:
        n = len(arr1)
        
        res = 0
        for p,q in [[1,-1],[-1,1],[1,1],[-1,-1]]:
            smallest = p * arr1[0] + q * arr2[0] + 0
            for i in range(1,n):
                x = arr1[i]*p+arr2[i]*q+i
                res = max(res,x-smallest)
                smallest = min(smallest,x)
        return res

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
        ###print(c1,c2,c3,c4,c5,c6,c7,c8)        
        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
        ###print(c1,c2,c3,c4,c5,c6,c7,c8)      
        
        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)