Максимальное произведение трех чисел для данного массива размера N

Question

Мне нужно написать программу, чтобы найти максимальное произведение трех чисел для данного массива размера N. Есть ли эффективный алгоритм для этого? Мне просто нужно знать алгоритм шагов. Ни один из алгоритмов, которые я думал, работает для всех тестовых случаев. Спасибо! FYI Array может содержать + ve, -ve или ноль элементов)

Answer 1

Найдите три самых больших числа в массиве (n1, n2, n3) и два самых маленьких числа (m1, m2).

Ответ либо n1 x n2 x n3, либо n1 x m1 x m2

Answer 2

Метод получения максимального произведения из 3 состоит в том, чтобы в основном находить самые большие 3 числа из массива и самые маленькие 2 числа из массива всего за одну итерацию по массиву.Есть, конечно, большое разнообразие решений, но это оптимальное 1, потому что время решения проблемы O (n), время других решений O (n lg n)

Вот код Java: кстати, есть гарантия, что входной массив не пустой и содержит минимум 3 элемента, поэтому нет необходимости в дополнительных проверках на пустоту и т. д.

  int solution(int[] a) {

/ * минимумы, инициализированные с maxint, чтобы избежать случаев с крайним максимумом в массиве и ложными минимумами 0 возвращенных минимумов * /

int min1 = Integer.MAX_VALUE;

int min2 = Integer.MAX_VALUE;

/* та же логика для максимальных инициализаций, но, конечно, инвертированная, чтобы избежать крайних минимальных значений в массиве и ложных 0 максимумов * /

    int max1 = Integer.MIN_VALUE;
    int max2 = Integer.MIN_VALUE;
    int max3 = Integer.MIN_VALUE;

// итерация по массиву

    for (int i = 0; i < a.length; i++) {

// test, если max1 меньше текущего значения массива

        if (a[i] > max1) {

/ * сохранить текущее значение max1 во временной переменной, чтобы позже проверить его по второму максимуму, как вы можете видеть, представляет собой цепочку изменений, есличДля самого большого максимума мы должны изменить 2 * /

            int tempMax1 = max1;

// назначить текущее значение массива как максимальное

            max1=a[i];

// проверить прежнее значение max1 maxMax1 против max2

            if(tempMax1>max2){

/ * сохранить значение max2 в значении tempMax2, чтобы проверить его по отношению к max3, и присвоить его максимуму 3, если оно больше * /

                int tempMax2 = max2;
                max2 =tempMax1;
                if(tempMax2>max3){
                    max3 = tempMax2;
                }

/ *, чтобы проверить, больше ли значение tempMax1, если оно большене больше, чем max3, это происходит, когда max1 получает новое значение, а старое значение max1 равно max2, но больше max3 * /

            }else{
                if(tempMax1>max3){
                    max3 = tempMax1;
                }
            }

/ * в случае, если ток a [i] не больше max1, мы тестируем его, чтобы увидеть, может быть, больше второго max.Затем та же самая логика сверху применяется здесь для max3 * /

        }else if(a[i]>max2){
            int tempMax2 = max2;
            max2 = a[i];
            if(tempMax2>max3){
                max3 =tempMax2;
            }

/ * наконец, если текущее значение массива не больше max1, а max2 может быть больше max3 * /

        }else if(a[i]>max3){
            max3 = a[i];
        }

/ * Логика сверху с максимумами применяется здесь с минимумами, но, конечно, инвертирована, чтобы обнаружить 2 минимума из текущего массива.* /

        if (a[i] < min1) {
            int tempMin1 = min1;
            min1 = a[i];
            if (tempMin1 < min2) {
                min2 = tempMin1;
            }
        } else if (a[i] < min2) {
            min2 = a[i];
        }
    }

/ * после того, как мы обнаружили 3 наибольших максимума и 2 наименьших минимума из массива, мы делаем 2 произведения из 3 от наибольшего максимума и 2 минимумов.Это необходимо, потому что математически произведение двух отрицательных значений является положительным значением, и из-за этого произведение min1 * min2 * max1 может быть больше, чем max1 * max2 * max3 и произведение, построенное из 3 максимумов.* /

    int prod1 = min1 * min2 * max1;
    int prod2 = max1 * max2 * max3;

// здесь мы просто вернем самый большой продукт

    return prod1 > prod2 ? prod1 : prod2;

}

Answer 3

Пожалуйста, используйте процедуру BubbleSort и делайте интервалы в течение трех итераций. Возьми дно три и умножь. Это должно предоставить вам решение.

int count = 0, j=a.length;  
boolean swap = false; 
do
{
  swap = false; 
  for(int i=1;i<j;i++)
  {
    if(a[i]<a[i-1])
    {
      int t= a[i];
      a[i] = a[i-1];
      a[i-1] = t; 
      swap = true;
    }
  }
  System.out.println(j+" Iteration:"+Arrays.toString(a));
  j--;
  if(swap)
    count++;
} while(swap && count<3); 
System.out.println(Arrays.toString(a));
return a[a.length-1]*a[a.length-2]*a[a.length-3];

Answer 4

Я написал это простое решение на Python, которое искал и не мог найти.

def ThreeHighestNumbers(arrayOfNumbers):
    PmaxNum1 = 0
    PmaxNum2 = 0 
    PmaxNum3 = 0
    NMinNum1 = 0
    NMinNum2 = 0
    maxNumber = 0

    for num in arrayOfNumbers:
        if num < 0:
            if num < NMinNum1:
                NMinNum2 = NMinNum1
                NMinNum1 = num
            elif num < NMinNum2:
                NMinNum2 = num
        else:
            if num > PmaxNum1:
                PmaxNum3 = PmaxNum2
                PmaxNum2 = PmaxNum1
                PmaxNum1 = num

            elif num > PmaxNum2:
                PmaxNum3 = PmaxNum2
                PmaxNum2 = num

            elif num > PmaxNum3:
                PmaxNum3 = num

    maxNumber = PmaxNum1 * PmaxNum2 * PmaxNum3

    if maxNumber == 0:
        return []

    if maxNumber < PmaxNum1 * NMinNum1 * NMinNum2:
        return [PmaxNum1,NMinNum2,NMinNum1]
    else:
        return [PmaxNum1,PmaxNum2,PmaxNum3]



arraOfNumbers = [1,2,3,4,5,6,-8,-9,0]
print ThreeHighestNumbers(arraOfNumbers)

Answer 5

def max_three_product(a):
a=sorted(a)
max_prod=a[-1]*a[-2]*a[-3]
if a[0]>0:
    return a[-1]*a[-2]*a[-3]
else:
    if a[0]*a[1]<0:
        return max_prod
    elif a[1]*a[2]>0:
        if a[0]*a[1]*a[-1]>max_prod:
            return a[0]*a[1]*a[-1]
        else:
            return max_prod
    else:
        if a[0]*a[1]*a[-1]>max_prod:
            return a[0]*a[1]*a[-1]
        else:
            return max_prod

Answer 6

Не эффективное решение, но полезное резервное копирование, чтобы показать использование структур данных. Создайте максимальную кучу и минимальную кучу из этих целых чисел. Затем удалите корень из максимальной кучи, пока вы не получите 3 различных целых числа (верхние 3) и не получите по крайней мере два различных целых числа из минимальной кучи. Выполните остальные проверки, как указано в других ответах max (max1 * max2 * max3, max1, min1, min2)

Answer 7

Это хорошее решение в Java:

class Solution {
    public int solution(int[] A) {
        int result1, result2;

        Arrays.sort(A);
        result1 = A[0] * A[1] * A[A.length-1];
        result2 = A[A.length-1] * A[A.length-2] * A[A.length-3];

        if (result1 >= result2) return result1;
        else return result2;

    }
}

Answer 8

Дан массив списка = (n1, n2, n3 ...). Вы можете сделать это за 3 прохода.

Let a1 = max (|n_i|) 
Let a2 = max (|n_i|) where n_i != a1

Теперь a1 * a2 либо положительное, либо отрицательное, либо равно нулю. Если ноль, то есть много решений; выберите любой n_i из остальных чисел. Если a1 * a2> 0, выберите наибольшее положительное число, в противном случае наименьшее отрицательное число. Более кратко, вы можете просто сделать один проход через остальную часть списка:

Let max_product = max (a1*a2*n_i) where n_i != a1 or a2