四个数组的值和索引和的最大绝对差

Question

您将获得四个数组A，B，C，D，每个数组的大小为N。查找给定下式的最大值（M）

M = max(|A[i] - A[j]| + |B[i] - B[j]| + |C[i] - C[j]| + |D[i] - D[j]| + |i -j|)
Where 1 <= i < j  <= N <br />

和这里| x |指x的绝对值。

约束

2 <= N <= 10^5  
1 <= Ai,Bi,Ci,Di <= 10^9

• 输入：N，A，B，C，D
• 输出：M

Ex.-

Input-   
5  
5,7,6,3,9  
7,9,2,7,5  
1,9,9,3,3  
8,4,1,10,5

输出-

25

Question picture

我已经尝试过这种方式

def max_value(arr1,arr2,arr3,arr4, n): 
    res = 0; 
    # Iterating two for loop,  
    # one for i and another for j. 
    for i in range(n): 
        for j in range(n):  
            temp= abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(arr3[i] - arr3[j]) + abs(arr4[i] - arr4[j]) + abs(i - j)
            if res>temp:
                res = res
            else:
                res = temp
    return res;

这是O（n ^ 2）。但是我想要一个更好的时间复杂度解决方案。对于更高的N，这将不起作用。

Here is solution for single array

给您四个数组A，B，C，D，每个数组的大小均为N。找到以下表达式的最大值（M）M = max（| A [i]-A [j] | + | B [i] -B [j] | + | C [i]-C [j] | + | D [i]-D [j] | + | i -j |）其中1 <= i ...

Answer 1

快速解决方案的想法

Answer 2

一个人可以针对您显示的单个阵列推广解决方案。给定数组的数量K，可以使2 ** (K+1)可能的数组组合摆脱绝对值。这样就很容易将各个组合的最大值和最小值分别进行比较。这是顺序O(n * 2**(K+1))，比您报告的值要好于O(n**2)。