给您四个数组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
例如-
Input-
5
5,7,6,3,9
7,9,2,7,5
1,9,9,3,3
8,4,1,10,5
输出-
24
我已经尝试过这种方式
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值。
可以将您展示的单个阵列的解决方案进行概括。给定许多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个向量中的哪个取为负数。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句