Z的最佳三元组是三个不同索引i、j和k的集合，其中i≤j≤k，这使得乘积Z[i]*Z[j]*Z/k]尽可能大

Question

我被要求使用分而治之来解决一个问题。问题是：设Z是n+个整数的数组，n≥3。Z的最佳三元组是三个不同索引i、j和k的集合，其中i<j<k、 这使得乘积Z[i]*Z[j]*Z/k]尽可能大。有什么想法可以用分而治之的方法解决这个问题吗。有什么想法我该怎么解决吗？

Answer 1

如果必须只使用Divide and Conquer来完成，除了在另一个关于使用Divide&Conquer进行选择的答案中提到的方法之外，我还可以想到一种方法。

您需要首先解决：

• 数组中的最大值，让我们调用它：

最大值(arr、开始、结束(

• 两个元素的最大乘积。让我们调用此方法：

maxTwoProduct(arr，start，end(

这可以使用Divide and Conquest来解决，比如：

int maxTwoProduct(arr, start, end):
if ( end - start + 1 < 2 ):
return MIN_VALUE
int mid = (end+start)/2;
max_11 = maximum(arr, start, mid);
max_12 = maxTwoProduct(arr, start, mid);
max_21 = maximum(arr, mid+1, end);
max_22 = maxTwoProduct(arr, mid+1, end);
return Math.max(max_11*max_21, max_12, max_22)

其想法是将数组分为两部分，maxTwoProduct可能以以下方式之一发生：

• 最大乘积可以完全在左部分中

• 最大产品可以完全在正确的部分

• 最大乘积可以是左部分最大值和右部分最大值的乘积

这可以扩展到maxThreeProduct，如下所示：

int maxThreeProduct(arr, start, end):
if ( end - start + 1 < 3 ):
return MIN_VALUE
int mid = ( end + start ) / 2;
maximum_11 = maximum(arr, start, mid);
maximum_12 = maxTwoProduct(arr, start, mid);
maximum_13 = maxThreeProduct(arr, start, mid);
maximum_21 = maximum(arr, mid+1, end);
maximum_22 = maxTwoProduct(arr, mid+1, end);
maximum_23 = maxThreeProduct(arr, mid+1, end);
return Math.max( maximum_11*maximum_22, maximum_12*maximum_21, maximum_13, maximum_23);

这里的最大值可以是以下四个选项之一：

• 最大三个乘积可以完全发生在左半中

• 它可以完全发生在的右半部分

• 它可以是左半部分的maxTwoProduct和最大值的乘积在的右半部分

• 它可以是右半部分的maxTwoProduct和最大值的乘积在左半

Answer 2

您不需要对数组进行排序来查找最大、第二大和第三大元素。你可以使用D&CO(n)选择算法。

同样值得注意的是，找到三个最大元素可以用O(3n) = O(n)复杂度的天真算法来完成。