0

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

给定一个整数数组和整数 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 --> 最终 AXBXCXD=30*10*10*10=30000

可能性 2

15+15+15+15=60 -->最终AXBXCXD=15*15*15*15=50625

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

另一个例子 N 是 8

数组是 2 个整数 4,2

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

2+2+2+2=8 最终输出 2X2X2X2= 16

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

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

4

1 回答 1

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

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

于 2018-09-26T17:27:43.723 回答