Учитывая 3 массива переменной длины, имеющих целые числа (положительные и отрицательные), найти максимальное произведение, которое можно сформировать путем умножения элемента, взятого из каждого массива.
Например.
A = [ 10, -10,15,-12];
B = [10, -12,13,-12];
C = [-11, -10, 9,-12];
Для вышеуказанных массивов: Максимальное произведение = 2160 с использованием 15, -12, -12.
Я пытался реализовать его, используя метод грубой силы 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]+".");
Мои мысли пока:
Я попытался подумать о сортировке массивов, но потом понял, что нам нужно сортировать по абсолютным значениям.
Затем я подумал об использовании элемента с максимальным абсолютным значением.
Но отсюда не может идти дальше о том, как выбрать следующие два для оптимизации решения.