arrays - 从三个数组中找到每个元素的最大乘积

Question

给定 3 个具有整数(正数和负数)的可变长度数组，找到可以通过将每个数组中的元素相乘而形成的最大乘积。

例如。

A = [ 10, -10,15,-12];
B = [10, -12,13,-12];
C = [-11, -10, 9,-12];

对于上述数组:使用 15、-12、-12 的最大乘积 = 2160。

我尝试使用三个嵌套 for 循环的蛮力方法 O(N^3) 来实现它但我正在寻找更优化的方法。

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]+".");

到目前为止我的想法:

我曾尝试考虑对数组进行排序，但后来意识到我们需要使用绝对值进行排序。 然后我想到使用具有最大绝对值的元素。

但无法从这里继续如何选择接下来的两个来优化解决方案。

Answer 1

一个选项是对所有三个数组进行排序，每个数组花费 O(nlogn) 时间(这不是嵌套的)，然后将每个已排序数组中最积极和消极的元素放入另一个数组中，您也对其进行排序O(nlogn) 时间。

此时，您可以只检查 6 元素数组，看看三个最正元素的乘积是否大于最正元素和两个最负元素的乘积，并返回该结果。