gpt4 book ai didi

algorithm - 从数组中找到四个总和为给定 N 的整数,并且这些整数需要最大化它们的最终产品

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:09:07 25 4
gpt4 key购买 nike

请注意,我不是在这里要求代码,但如果可能的话,我正在寻求一种方法和解释。

给定一个整数数组和整数 N,我们如何才能找到恰好四个整数,它们相加后将等于 N。有一个条件,我们应该找到四个这样的整数 A、B、C、D,它们将使产品最大化

AXBXCXD

例子 N 是 60 并且数组是

30,20,15,12,10,6,5,4,3,2

找到四个整数有很多种可能性,其中一些如下所示

可能性1

30+10+10+10=60 --> final AXBXCXD=30*10*10*10=30000

可能性2

15+15+15+15=60 -->final AXBXCXD=15*15*15*15=50625

在所有可能的 A、B、C、D 整数集及其乘积中,正确答案是 50625,它必须是我们的最终输出。

另一个例子N是8

Array is of 2 integers 4,2

四个整数A,B,C,D求和的可能性只有一个,如下。

2+2+2+2=8 final output 2X2X2X2= 16

如果 array 没有这样的四个整数的可能组合来加起来为 N,我们实际上必须打印 -1。这就是数组没有这种可能的整数的地方。

通过查看 at this question我了解我们如何递归地解决问题以找出总和为 N 的数组子集。但我不明白我们如何从上述问题陈述中强制执行确切的四个整数条件。

最佳答案

  • 计算每对及其乘积的总和
  • 按总和排序
  • 对于求和 X 的每一对,找到求和 N - X 且乘积最高的那对
  • 将 2 对的乘积存储为该值与前一个最大值之间的最大值
  • 完成后,显示最大产品

复杂度:O(n^2 * 2 log n)。

关于algorithm - 从数组中找到四个总和为给定 N 的整数,并且这些整数需要最大化它们的最终产品,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52522222/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com