Multiplikation von Elementen in einem Array

Question

Ich versuche, ein Problem zu lösen. Wir werden das maxProduct eines Arrays in O (n) finden, so dass keine doppelten for-Schleifen erlaubt sind, da es O (n²) wäre. Sie werden in meinem Code sehen, dass alle Elemente bis auf den ersten vervielfältigt sind und letzte Elemente. Wie kann ich das erste und letzte Element meines Arrays mit der Logik meines Codes multiplizieren?

hier ist mein Code:

public class Maxprod { 
public static void main(String [] args){ 
    Maxprod myclass = new Maxprod(); 
    myclass.maxProduct(); 
} 

public void maxProduct(){ 
    int [] myarr = {4, -5, -7, 5}; 
    int max = 0, p=0; 
    int q = 0; 

    for(int i=0; i <myarr.length-1; i++){ 
     p = myarr[i]*myarr[i+1]; // 4 * 5 is missing here 
     if (p > max){ 
      max = p; 
     } 
    } 
    System.out.println(max); 
} 

} 

Answer 1

Ihr Code Situation scheint schlimmer als gedacht; Von dem, was ich sehe, vermisst du nicht nur (4 * 5), sondern auch (4 * -7) und (-5 * -5). Sind Sie sicher, dass Sie nur fortlaufende Nummern möchten? Sie verpassen auch (-7 * 5), weil Ihre Bedingung für die for-Schleife um eins deaktiviert ist.

Um Ihre direkte Frage zu beantworten, initialisieren p (Start * end):

p = myarr[0] * myarr[myarr.length-1]; 
for(int i=0; i <myarr.length; i++){ 
    p = myarr[i]*myarr[i+1]; // 4 * 5 is missing here 
    if (p > max){ 
     max = p; 
    } 
} 
System.out.println(max); 

Wenn Sie tatsächlich maxProduct wollen, alle Permutationen bedenkt, in O (n), werden Sie die Spur müssen zwei größte positive und zwei größte negative Zahlen. Betrachten Sie etwas in der Art:

public void maxProduct(){ 
    int [] myarr = {4, -5, -7, 5}; 
    int max = 0, maxn = 0, maxp = 0; 
    int n1 = 0, n2 = 0; 
    int p1 = 0, p2 = 0; 

    for(int i=0; i <myarr.length; i++){ 
     // Store greatest negative pair 
     if (myarr[i] < n1) { 
      n2 = n1; 
      n1 = myarr[i]; 
     } 

     // Store greatest positive pair 
     if (myarr[i] > p1) { 
      p2 = p1; 
      p1 = myarr[i]; 
     } 
    } 

    maxn = n1 * n2; 
    maxp = p1 * p2; 
    if (maxn > maxp) { 
     max = maxn; 
    } else { 
     max = maxp; 
    } 

    System.out.println(max); 
}