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

Question

给定四个大小为 N 的数组 A、B、C、D。
找到下面给出的表达式

的最大值 (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

例如-

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

输出-

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

Answer 1

更快解决的想法

如果您只对 M 的最大值感兴趣，您可以搜索 A、B、C、D 和 i-j.Let 的最小值和最大值，也就是说 i_Amax 是i 为 A 的最大值的索引。
现在您找到 B[i_Amax]、C[i_Amax]...的值，i_Amin 的值也是如此，并计算 M 与最大值的差值和最小值。
你用 B 的最大值的索引重复了之前的步骤，所以 i_Bmax 并计算 M，你重复直到你通过 A,B,C,D 和 i-j
您现在应该有五项，其中一项应该是最大值

如果您没有明确的最小值或最大值，则必须计算所有可能的最小值和最大值的索引。

我觉得应该能找到任意最大值，而且比n^2快，尤其是大n，但是我自己没有实现，所以你得想一想，看看我是不是逻辑错误和一个用这个想法找不到每个最大值。

希望对您有所帮助！

Answer 2

可以概括您展示的单个数组的解决方案。给定 K 个数组，包括索引数组，可以使 2**K 个可能的数组组合来去除绝对值。然后很容易分别取每个组合的最大值和最小值并进行比较。这是 O(Kn*2^K) 的阶数，比您报告的值的原始 O(Kn^2) 好得多。

这是一个适用于任意数量输入数组的代码。

import numpy as np

def run(n, *args):
    aux = np.arange(n)

    K = len(args) + 1
    rows = 2 ** K
    x = np.zeros((rows, n))
    for i in range(rows):
        temp = 0
        for m, a in enumerate(args):
            temp += np.array(a) * ((-1) ** int(f"{i:0{K}b}"[-(1+m)]))
        temp += aux * ((-1) ** int(f"{i:0{K}b}"[-K]))
        x[i] = temp

    x_max = np.max(x, axis=-1)
    x_min = np.min(x, axis=-1)
    res = np.max(x_max - x_min)
    return res

for 循环也许值得更多解释：为了做出所有可能的绝对值组合，我将每个组合分配给一个整数，并依靠该整数的二进制表示来选择其中的哪些组合K个向量必须取负数。

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

Maximum absolute difference of value and index sums of Four arrays

python

arrays

algorithm

absolute

difference

更快解决的想法