从三个数组中找出元素的最大乘积
从三个数组中找出元素的最大乘积
提问于 2019-06-10 13:32:07
给定3个具有整数(正数和负数)的可变长度数组，可以通过乘积每个数组中的一个元素来找到最大乘积。
例如：
A = [ 10, -10,15,-12];
B = [10, -12,13,-12];
C = [-11, -10, 9,-12];上述数组的：使用15、-12、-12.的最大乘积= 2160
我尝试使用蛮力方法O(N^3)实现它，使用三个嵌套的for循环，但我正在寻找更优化的方法。
int[] A = new int[]{10,-10,15,-12};
int[] B = new int[]{10,-12,13,-12};
int[] C = new int[]{-11,-10,9,-12};
int max = Integer.MIN_VALUE;
int pos[][]=new int[3][2];
for (int i=0; i < A.length ; i++ ){
for (int j=0; j < B.length ; j++ ){
for (int k=0; k < C.length ; k++ ){
int prod = A[i] * B[j] * C[k];
if( prod > max ){
max = prod;
pos[0][0]=i;
pos[1][0]=j;
pos[2][0]=k;
pos[0][1]=A[i];
pos[1][1]=B[j];
pos[2][1]=C[k];
}
}
}
}
System.out.println("Maximum product = "+max+" using "+pos[0][1]+", "+pos[1][1]+", "+pos[2][1]+".");到目前为止，我的想法：
我曾尝试过排序数组，但后来意识到我们需要使用绝对值进行排序。然后，我考虑使用具有最大值的元素。
但无法从这里向前推进，如何选择下两个方案来优化解决方案。
回答 2
Stack Overflow用户
发布于 2019-06-10 13:43:44
一个选项是对所有三个数组进行排序，这需要花费O(nlogn)时间(这不是嵌套的)，然后将每个排序数组中最正负的元素放到另一个数组中，您也可以为O(nlogn)时间进行排序。
此时，您只需在6元素数组中签入，查看三个最正元素的乘积是否大于最正元素和两个最负元素的乘积，并返回结果。
Stack Overflow用户
发布于 2019-06-10 17:08:01
有四种方法可以形成最大的产品：
- 从这三个数组中每一个取最大值
- 从第一个数组取最大值，从第二个和第三个数组取最小值。
- 从第二个数组取最大值，从第一个和第三个数组取最小值。
- 从第三个数组取最大值，从第一个和第二个数组取最小值。
您可以通过排序或通过对数组进行顺序扫描来找到最小和最大元素。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56527448
复制相关文章
相似问题
腾讯云开发者
