Maksymalny iloczyn trzech liczb dla danej macierzy wielkości N

Question

Potrzebuję napisać program, aby znaleźć maksymalny iloczyn trzech liczb dla danej tablicy o rozmiarze N. Czy istnieje jakiś skuteczny algorytm dla tego? Po prostu muszę znać kroki algorytmu. Nie algorytmów, które myślałem, działa dla wszystkich przypadków testowych. Dzięki! Tablica FYI może zawierać elementy + ve, -ve lub zero)

Answer 1

Znajdź trzy największe liczby w tablicy (n1, n2, n3) i dwie najmniejsze liczby (m1, m2).

Odpowiedź jest zarówno N1 x x N2 N3 lub n1 x m1 x m2

Answer 2

Biorąc pod tablicą listy = (N1, N2, N3 ...). Możesz to zrobić w 3 przejściach.

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

Teraz a1 * a2 jest albo dodatnie, ujemne, albo zero. Jeśli zero, to istnieje wiele rozwiązań; wybierz dowolne n_i z pozostałych liczb. Jeśli a1 * a2> 0, wybierz największą liczbę dodatnią, w przeciwnym razie najmniejszą liczbę ujemną. Bardziej zwięźle, można po prostu zrobić jedno przejście przez resztę listy:

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

Answer 3

Sposób uzyskać max produktem 3 składa się w zasadzie znaleźć największe 3 numery z tablicy i najmniejsze 2 numery z tablicy w zaledwie 1 iteracji na tablicy. Istnieje oczywiście wiele różnych rozwiązań, ale jest to optymalne 1, ponieważ czas na rozwiązanie problemu to O (n), innym rozwiązaniem jest czas O (n lg n)

Oto kod Java: przy okazji jest gwarancja, że ​​tablica wejściowa nie jest pusta i zawiera minimum 3 elementy, więc nie ma potrzeby dodatkowych kontroli pustych i tak dalej.

int solution(int[] a) { 

/* minima inicjalizowane max Int do uniknięcia sytuacji, z najwyższą max w tablicy i fałszywie minim 0 minimalne zwrócone */

Int MIN1 = Integer.MAX_VALUE;

int min2 = Integer.MAKSYMALNA WARTOŚĆ;

/* to samo rozumowanie dla maksymalnego inicjalizacji ale oczywiście odwrócić, aby uniknąć minimum wartości skrajnych w tablicy, a maksima fałszywe 0 */

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

// iteracji na matrycę

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

// sprawdź, czy wartość max1 jest mniejsza niż bieżąca wartość tablicy

 if (a[i] > max1) { 

/* zapisz m AX1 wartość prądu w var temp przetestować go później na drugim maksymalnej tutaj jak widać to łańcuch zmian, jeśli zostanie zmieniony największy max musimy zmienić drugi 2 */

  int tempMax1 = max1; 

// przypisanie bieżąca wartość array jako maksymalną

  max1=a[i]; 

// Test tempMax1 dawnej wartości max1 przeciwko Max2

  if(tempMax1>max2){ 

/* sklep wartości max2 wartości tempMax2 przetestować go ag ainst max3 i przypisać go do max 3, jeśli jest większy */

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

/* test, aby sprawdzić, czy tempMax1 jest większy, jeśli nie jest większy niż MAX3, że to się dzieje, gdy max1 dostaje nową wartość i stare wartość max1 jest równoznaczne z Max2 ale większy niż MAX3 */

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

/* w przypadku, gdy prąd a [i] jest nie większy niż max1 testujemy go zobaczyć może jest większy niż drugiego max. Potem ten sam układ logiczny z powyżej stosuje się tutaj do max3 */

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

/* w końcu, gdy bieżąca wartość tablica nie jest większy niż max1 i Max2 może być większa niż max3 */

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

/* Logika z góry z maksimum jest tu stosowana z minimum, ale oczywiście odwrócona na odkryć 2 minimalne wartości z bieżącej tablicy. */

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

/* po odkryliśmy 3 największe maksima i 2 najmniejsze minima z tablicy to zrobić 2 produkty 3 z największą maksymalną i 2 minima. Jest to konieczne, ponieważ matematycznie iloczyn 2 ujemnych wartości jest wartością dodatnią, a ponieważ to iloczyn min1 * min2 * max1 może być większy niż max1 * max2 * max3 i produkt zbudowany z 3 maksimów.*/

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

// tutaj po prostu wrócić największy produkt

return prod1 > prod2 ? prod1 : prod2; 

} 

Answer 4

Jest to dobre rozwiązanie w Javie:

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 5

Nie skutecznym rozwiązaniem, ale przydatna do tworzenia kopii zapasowych pokaż wykorzystanie struktur danych. Utwórz maksymalną liczbę stert i minę z tych liczb całkowitych. Następnie usuń root z maks. Stosu, aż uzyskasz 3 różne liczby całkowite (3) i zdobądź co najmniej dwie różne liczby całkowite z min sterty. Czy resztę kontroli jak wspomniano w innych odpowiedzi Max (max1 * max2 * max3, max1, MIN1, min2)

Answer 6

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 7

Napisałem to proste rozwiązanie w Pythonie, które szukałem i mogłyśmy znaleźć.

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 8

Proszę użyć procedury BubbleSort i podzielić na trzy iteracje. Zrób trzy dno i pomnóż. To powinno dostarczyć ci rozwiązania.

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];