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

苏南·库马尔·苏南

给您四个数组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

例如-

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值。

这是单阵列的解决方案

詹卢卡·米奇(Gianluca Micchi)

可以将您展示的单个阵列的解决方案进行概括。给定许多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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

制作四个加和成最大值的随机数

来自分类Dev

Javascript-如何返回数组中最大的四个数字?

来自分类Dev

在数组中寻找最大值;在 Java 中使用四个线程

来自分类Dev

以随机顺序查看接下来的四个数字(使用srand和rand)

来自分类Dev

查找等于R中的和的四个数字的所有组合

来自分类Dev

在mysql的四个表中找到最大值

来自分类Dev

MSSQL获取ID和四个日期的最小值(最早)

来自分类Dev

如果填写了四个文本框,则计算和更新值

来自分类Dev

带有 ggplot2、一个分类变量和四个数字的图形

来自分类Dev

如何从PHP中的另一个数组添加新的索引和值?

来自分类Dev

从pandas数组中获取N个最大值,并保留索引和列标题

来自分类Dev

显示两行和每行四个项目

来自分类Dev

javascript:将2个数组与属性和索引合并

来自分类Dev

给定2个数组,找到索引乘法的最小和

来自分类Dev

javascript:将2个数组与属性和索引合并

来自分类Dev

获取起始索引和终止索引之间的数组最大值和最小值

来自分类Dev

获取起始索引和终止索引之间的数组最大值和最小值

来自分类Dev

显示数组中的最大值和索引号

来自分类Dev

如何在内核的一个数组中连接四个整数?

来自分类Dev

当我 console.log(portfoliosArray) 它返回一个数组或四个数组?

来自分类Dev

如何将第二个和第四个数字(逗号前)转换为双精度?C程序设计

来自分类Dev

最大和最小的四个整数(无数组,无函数,最少的“ if”语句)

来自分类Dev

比较一个数组值和另一个数组

来自分类Dev

最小化和差的绝对值

来自分类Dev

函数如何使用oracle中的集合返回第二个和第四个值?答案是 42 和 46

来自分类Dev

给定没有重复值和目标和的数组,如何查找4个数字的和?

来自分类Dev

向数组中插入绝对差后,找到数组中的第k个最大元素

来自分类Dev

给定1至10个元素的数组的4个数字。查找3个数字,它们的总和可以生成所有四个数字?

来自分类Dev

具有四个字段的数组的唯一值

Related 相关文章

  1. 1

    制作四个加和成最大值的随机数

  2. 2

    Javascript-如何返回数组中最大的四个数字?

  3. 3

    在数组中寻找最大值;在 Java 中使用四个线程

  4. 4

    以随机顺序查看接下来的四个数字(使用srand和rand)

  5. 5

    查找等于R中的和的四个数字的所有组合

  6. 6

    在mysql的四个表中找到最大值

  7. 7

    MSSQL获取ID和四个日期的最小值(最早)

  8. 8

    如果填写了四个文本框,则计算和更新值

  9. 9

    带有 ggplot2、一个分类变量和四个数字的图形

  10. 10

    如何从PHP中的另一个数组添加新的索引和值?

  11. 11

    从pandas数组中获取N个最大值,并保留索引和列标题

  12. 12

    显示两行和每行四个项目

  13. 13

    javascript:将2个数组与属性和索引合并

  14. 14

    给定2个数组,找到索引乘法的最小和

  15. 15

    javascript:将2个数组与属性和索引合并

  16. 16

    获取起始索引和终止索引之间的数组最大值和最小值

  17. 17

    获取起始索引和终止索引之间的数组最大值和最小值

  18. 18

    显示数组中的最大值和索引号

  19. 19

    如何在内核的一个数组中连接四个整数?

  20. 20

    当我 console.log(portfoliosArray) 它返回一个数组或四个数组?

  21. 21

    如何将第二个和第四个数字(逗号前)转换为双精度?C程序设计

  22. 22

    最大和最小的四个整数(无数组,无函数,最少的“ if”语句)

  23. 23

    比较一个数组值和另一个数组

  24. 24

    最小化和差的绝对值

  25. 25

    函数如何使用oracle中的集合返回第二个和第四个值?答案是 42 和 46

  26. 26

    给定没有重复值和目标和的数组,如何查找4个数字的和?

  27. 27

    向数组中插入绝对差后,找到数组中的第k个最大元素

  28. 28

    给定1至10个元素的数组的4个数字。查找3个数字,它们的总和可以生成所有四个数字?

  29. 29

    具有四个字段的数组的唯一值

热门标签

归档