Finden Sie maximale Produkt der 3 zahlen in einem array

Gegeben ein array von ganzen zahlen, die enthalten beide +ve-und -ve-zahlen. Ich habe zu maximieren, das Produkt 3 Elemente des Arrays. Die Elemente können nicht zusammenhängend.

Einige Beispiele:

int[] arr = { -5, -7, 4, 2, 1, 9};  //Max Product of 3 numbers = -5 * -7 * 9
int[] arr2 = {4, 5, -19, 3};       //Max Product of 3 numbers = 4 * 5 * 3

Ich habe versucht es zu lösen mit Dynamische Programmierung, aber ich bin nicht immer das erwartete Ergebnis. Es ist wieder das Ergebnis oft mit der gleichen Nummer zweimal in die Multiplikation. Also, für die array - {4, 2, 1, 9} ist es die Rückkehr - 32, die 4 * 4 * 2.

Hier ist mein code:

public static int maxProduct(int[] arr, int count) {
    return maxProduct(arr, 0, arr.length - 1, count);
}

private static int maxProduct(int[] arr, int fromIndex, int toIndex, int count) {

    if (count == 1) {
        return maximum(arr, fromIndex, toIndex);
    } else if (toIndex - fromIndex + 1 < count) {
        return 1;
    } else {
        return MathUtil.max(maxProduct(arr, fromIndex, toIndex - 1, count - 1) * arr[toIndex - 1], 
                            maxProduct(arr, fromIndex, toIndex - 1, count));
    }
}

MathUtil.max(int a, int b) ist eine Methode, die gibt maximal a und b.
Die beiden Werte, die ich übergeben, um max Methode gibt es:
- maxProduct, wenn wir Bedenken, das Letzte element als ein Teil des Produktes.
- maxProduct, wenn wir nicht betrachten es als ein Teil des Produktes.
count enthält die Anzahl der Elemente, die wir betrachten wollen. Hier 3.
Für count == 1 suchen wir noch maximal 1 element aus dem array. Das bedeutet, wir verwenden die maximale array-element.
Wenn toIndex - fromIndex + 1 < count, bedeutet, es gibt nicht genug Elemente im array zwischen diesen Indizes.

Ich habe eine intuition, dass der erste if Zustand ist einer der Gründe des Scheiterns. Weil, es ist nur wenn man maximale element aus einem array, während das maximale Produkt kann aus negativen zahlen zu. Aber ich weiß nicht, wie zu kümmern.

Der Grund, warum ich mit Hilfe der Dynamischen Programmierung ist, dass ich dann verallgemeinern Sie diese Lösung, um für jeden Wert von count. Natürlich, wenn jemand irgendeine bessere Annäherung, auch für count = 3 begrüße ich den Vorschlag (ich möchte vermeiden, Sortieren Sie das array, so dass ein weiteres O(nlogn) zumindest).

Möchten Sie, dass der maximale absolute Wert? I. e., 35 eine "höhere" Produkt als -49?
Ja. Maximale Produkt, nicht maximale absolute Produkt.
Ihr Algorithmus mit recursion können Sie hinzufügen if Zustand zu überprüfen fromIndex und toIndex mit entsprechenden return, kann wieder 1, Sie könnten Ihre Arbeit getan.
Ich verstehe es nicht. Ich habe bereits einen base-case-Betrachtung die Werte der fromIndex und toIndex. Tun Sie wollen mich zu der überlegung, einen anderen Fall?
Ja, ich denke, das ist, was Sie brauchen. Wenn Ihre Multiplikation geschieht mit der gleichen array element, dann seine bug im code, und Sie sollten aufpassen, dass case wo fromIndex und toIndex sind die gleichen.

InformationsquelleAutor user3011937 | 2013-12-12

10

Sortieren Sie das gegebene array in aufsteigender Reihenfolge, und nehmen Sie die maximale in diesen Fällen
um die Antwort zu erhalten..
1. Produkt der letzten 3 zahlen in sortierter array
2. Produkt der ersten beiden und die Letzte Zahl in der sortierten array
Sie könnten auch in der Lage sein, dies zu tun, ohne das Sortieren durch Iteration über das array einmal und einfach nur die Speicherung der drei größten/kleinsten Werte.
was ist mit negativen Werten
zahlen würde abgedeckt werden, der zweite Punkt ...
habe es Dank, btw, das ist meine Lösung in Javascript github.com/doron2402/algorithm-interviews/blob/master/...
was ist, wenn alle Elemente negativ sind? Ich denke, das wird nicht funktionieren. Sollten wir auch überprüfen Sie die ersten 3 Elemente " - Produkt?

InformationsquelleAutor Srinath
6

Für count=3, Ihre Lösung wird 1 der 3 Formen:
1. Die 3 größte positive Werte (vorausgesetzt, es gibt 3 positive Werte)
2. Den größten positiven Wert und die 2 kleinsten negativen Werte (vorausgesetzt, es gibt einen positiven Wert)
3. Den 3 am wenigsten negativen Werte
Jeder von denen kann gelöst werden viel einfacher als mit DP.

Es könnte auch 2 positive Werte und 1 negativer Wert; betrachten den trivialen Fall, { -1, 1, 2 }.
Vorausgesetzt, Sie sind unter der Annahme absoluter Werte, gemessen an #3, wird es einen vierten Fall, der die 2 größten zahlen und die geringsten negativen Zahl, in diesem Fall bricht alles zusammen an einem Fall, das ist die 3 zahlen, die am weitesten von 0.
Frey: ich war nicht der Annahme absoluter Werte; für #3, ich meinte die negative w/ den KLEINSTEN absoluten Wert (wenn alle Werte negativ sind, wird Ihr Ergebnis wird negativ sein, so dass Sie Schießen, die negativen, die 0 am nächsten ist).
Ah, ich sehe.
So haben wir zum iterieren über das array für alle 3 Fälle, und dann herauszufinden, die 3 Werte für alle? Keine einfache Möglichkeit?

InformationsquelleAutor Scott Hunter

Ist es immer max(kleinste zwei negative Ziffern und größte positive oder
letzten drei die große positive zahlen)

public static void main(String args[]){

    int array[] = { -5,-1,4,2,1,9};
    Arrays.sort(array);

    int length = array.length;
    System.out.println(max(array[0]*array[1]*array[length-1], 
                           array[length-1]*array[length-2]*array[length-3]));   
}

InformationsquelleAutor Sumedha Khatter

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ComputeMaxProduct {
    public static void main(String[] args){

        int [] arr = {4, 5, -19, 3};

        List<Integer> superSet = new ArrayList<>();

        for (int a : arr ){
        superSet.add(a);
        }

        int k = 3;

        int maxProduct = computeMaxProduct(superSet, k);
        System.out.println("maximum product is : " + maxProduct);
    }

    private static int computeMaxProduct( List<Integer> superSet, int k ){
        List<Set<Integer>> res = getSubsets(superSet,k);
        int maxProduct = 1;
        for(int index = 0; index < res.size(); index++){
        int product = 1;
        for(Integer i : res.get(index)){
            product *= i;
        }

        if (product > maxProduct){
            maxProduct = product;
        }
        }

    return maxProduct;
    }


    private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
        //successful stop clause
        if (current.size() == k) {
            solution.add(new HashSet<>(current));
            return;
        }
        //unseccessful stop clause
        if (idx == superSet.size()) return;
        Integer x = superSet.get(idx);
        current.add(x);
        //"guess" x is in the subset
        getSubsets(superSet, k, idx+1, current, solution);
        current.remove(x);
        //"guess" x is not in the subset
        getSubsets(superSet, k, idx+1, current, solution);
    }

    public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
        List<Set<Integer>> res = new ArrayList<>();
        getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
        return res;
    }
}

InformationsquelleAutor openmike

public class MaxProdofThreenumbers {
public int ThreeLargeNumbers(int[] a) {
int topfirstpos = 0;
    int topsecpos = 0;
    int topthirdpos = 0;
    int topfirstneg = 0;
    int topsecneg = 0;
    int prodneg = 0;
    int prodpos = 0;
    int prodmax = 0;
    boolean flag = false;
for (int i = 0; i < a.length; i++) {
        String num = a[i] + "";
        if (num.contains("-")) {
            String array[] = num.split("-");
            num = array[1];
            flag = true;
        } else 
            flag = false;
        if (flag) {
            if (topfirstneg < Integer.valueOf(num)) {
                topsecneg = topfirstneg;
                topfirstneg = Integer.valueOf(num);
            } else if (topsecneg < Integer.valueOf(num)) {

                topsecneg = Integer.valueOf(num);
        }
    }
        else {
            if (topfirstpos < Integer.valueOf(num)) {
                topsecpos = topfirstpos;
                topfirstpos = Integer.valueOf(num);
            }
        else if (topsecpos < Integer.valueOf(num)) {
                topthirdpos = topsecpos;
                topsecpos = Integer.valueOf(num);
            }
            else if (topthirdpos < Integer.valueOf(num)) {
                topthirdpos = Integer.valueOf(num);
            }
        }
    }
    prodneg = topfirstneg * topsecneg;
    prodpos = topfirstpos * topsecpos;

    if (prodneg > prodpos) {
        prodmax = prodneg * topfirstpos;
    } else {
        prodmax = prodpos * topthirdpos;
    }
    return prodmax;
}

public static void main(String a[]) {
    int list[] = { -29, 3, -2, -57, 8, -789, 34 };
MaxProdofThreenumbers t = new MaxProdofThreenumbers();
System.out.println(t.ThreeLargeNumbers(list));

}

}

Es ist nützlich, wenn Sie können hinzufügen, einige zusätzliche Informationen über Ihre Methodik

InformationsquelleAutor Midhula Kadiyala

1
```
n=len(arr1)
    for i in range(0,n):
        arr1[i]=abs(arr1[i])
    arr1.sort()
    return arr1[n-1]*arr1[n-2]*arr1[n-3]
```
obwohl diese Lösung ist einfach dies beinhaltet im wesentlichen die Sortierung des Arrays und dann mit dem Produkt der letzten drei zahlen , bevor Sie zu tun ist ; alle Werte in das array sollte positiv sein .das geschieht durch die erste for-Schleife.

InformationsquelleAutor ravi tanwar

package interviewProblems;

import interviewProblems.exceptions.ArrayTooSmallException;
import java.util.PriorityQueue;

public class Problem5 {

    public static void main(String[] args) {

        int[] data1 = new int[]{};                                  //error
        int[] data2 = new int[]{1, 5};                              //error
        int[] data3 = new int[]{1, 4, 2, 8, 9};                     //Case: all positive --> 3-max
        int[] data4 = new int[]{10, 11, 12, -20};                   //Case: 1 negative   --> 3-max
        int[] data5 = new int[]{ -5, -6, -10, 7, 8, 9};              //Case: 2+ negative  --> 3-max || 1-max 2-small
        int[] data6 = new int[]{ -12, -10, -6, -4};                  //Case: all negative --> 3-max

        int[] data7 = new int[]{ -10, -10, 1, 3, 2};
        try {
            productOfThree(data2);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        try {
            System.out.println(productOfThree(data3));
            System.out.println(productOfThree(data4));
            System.out.println(productOfThree(data5));
            System.out.println(productOfThree(data6));
            System.out.println(productOfThree(data7));
        } catch (Exception e) {
            System.out.println("You should not see this line");
        }

    }

    // O(n) time
    // O(1) memory
    private static int productOfThree(int[] data) throws ArrayTooSmallException {
        if (data.length < 3) {
            throw new ArrayTooSmallException(3 , data.length);
        }

        PriorityQueue<Integer> maxNumbers = new PriorityQueue<>();                  //keep track of 3 largest numbers
        PriorityQueue<Integer> minNumbers = new PriorityQueue<>((x, y) -> y - x);   //keep track of two smallest numbers

        for (int i = 0; i < data.length; i++) {
            maxNumbers.add(data[i]);
            minNumbers.add(data[i]);
            if(maxNumbers.size() > 3) {
                maxNumbers.poll();
            }
            if(minNumbers.size() > 2){
                minNumbers.poll();
            }
        }

        int maxLow = maxNumbers.poll();
        int maxMed = maxNumbers.poll();
        int maxHigh = maxNumbers.poll();

        int minHigh = minNumbers.poll();
        int minLow = minNumbers.poll();

        int possibleProduct1 = maxHigh * maxMed * maxLow;
        int possibleProduct2 = maxHigh * minHigh * minLow;

        return Math.max(possibleProduct1, possibleProduct2);
    }

// O(n) time
// O(n) memory
//   private static int productOfThree(int[] data) throws ArrayTooSmallException {
//       if(data.length < 3) {
//           throw new ArrayTooSmallException("Array must be at least 3 long to preform productOfThree(int[] data)");
//       }
//
//       PriorityQueue<Integer> maxNumbers = new PriorityQueue<>((x , y) -> y - x);    //keep track of 3 largest numbers
//       PriorityQueue<Integer> minNumbers = new PriorityQueue<>();                    //keep track of two smallest numbers
//
//       for(int i = 0; i < data.length; i++) {
//           maxNumbers.add(data[i]);
//           minNumbers.add(data[i]);
//       }
//
//       int maxHigh = maxNumbers.poll();
//       int maxMed = maxNumbers.poll();
//       int maxLow = maxNumbers.poll();
//
//       int minLow = minNumbers.poll();
//       int minHigh = minNumbers.poll();
//
//       int possibleProduct1 = maxHigh * maxMed * maxLow;
//       int possibleProduct2 = maxHigh * minHigh * minLow;
//
//       return Math.max(possibleProduct1 , possibleProduct2);
//   }

}

https://github.com/amilner42/interviewPractice/blob/master/src/interviewProblems/Problem5.java

InformationsquelleAutor Arie Milner

0

Dieses problem getan werden kann, in O(n) Zeit.

Verfolgen diese 5 Variablen und aktualisieren Sie Sie während jeder iteration:
1. höchste Produkt der 3 zahlen
2. höchsten Produkt von 2 zahlen
3. höchste element
4. niedrigsten Produkt von 2 zahlen
5. niedrigsten element
Nach der letzten iteration, ein Produkt von 3 zahlen-variable wird die Antwort sein.

Wie unterscheidet sich dies von Scott Hunter ' s Antwort, mit der Fall für 2 positive values and 1 negative value geändert?

InformationsquelleAutor user4259055
0

Unter der Annahme, dass eine positive Produkt ist größer als das negative Produkt, das ich denken kann auf folgende Weise getan werden kann.
1. Wenn es weniger als zwei negativen Elementen in dem array, dann ist es einfacher, ein Produkt von top 3(top == positiven) Elemente.
2. Wenn negative zahlen sind so gewählt, mindestens 2 von Ihnen müssen in das Produkt, so ist das Produkt positiv. Also was auch immer der Fall sein, den oberen (positiven) Zahl wird immer Teil des Produktes.
3. Multiplizieren beiden letzten(negativen) und der 2. und 3. höchsten(positiven) und vergleichen. Von diesen zwei Paaren je höher der Wert, wird ein Teil des fertigen Produkts zusammen mit den oben positiver auf die shortlist in der Zeile darüber.
InformationsquelleAutor tick_tack_techie
0

https://stackoverflow.com/users/2466168/maandoo 's Antwort ist die beste.

Als er sagte, die Antwort ist max(l,r) für
```
r. product of last 3 numbers in sorted array
l. product of first two and last number in the sorted array
```
Lassen Sie mich aufwendige jetzt.

Ich denke, das problem ist Verwirrung, weil jede Zahl kann positiv, negativ und null. 3 Staat ist lästig zu verwalten, die durch Programmierung, wissen Sie!

Fall 1) Gegebenen drei zahlen
- Verwenden Sie alle
Fall 2) Gegebenen vier zahlen
- Positive Zahl ist, zeigen + Negative Zahl ist, zeigen -.
- Zahlen werden von rechts nach Links sortiert werden.
Fall 2-1)
```
2-1) ---- => r (answer is negative)
2-2) ---+ => l (answer is positive)
2-3) --++ => l (answer is positive)
2-4) -+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)
```
Wenn a 0 ist, gemischt in vier zahlen, kommt es zwischen
- und +.

Fall 2-2)
Angenommen, kleinste + war eigentlich 0.
```
2-1) ---- => r (answer is negative)
2-2) ---0 => l (answer is 0)
2-3) --0+ => l (answer is positive)
2-4) -0++ => r (answer is 0)
2-5) 0+++ => r (answer is positive)
```
Fall 2-3)

Angenommen, größte - war eigentlich 0.
```
2-1) ---0 => r (answer is 0)
2-2) --0+ => l (answer is positive)
2-3) -0++ => l (answer is 0)
2-4) 0+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)
```
Fall 2-4)

Wenn mehr als zwei 0 ist gemischt, Produkte wird immer 0, da
```
-00+
```
Zusammenfassung Fall 2)

Antwort ist übereinstimmend Fall 2-1 ~ 2-4.
```
2-1) r (negative or 0)
2-2) l (0 or positive)
2-3) l (0 or positive)
2-4) r (0 or positive)
2-5) r (positive)
```
So, wir brauchen uns nicht sorgen zu machen über die 0 eigentlich.

Fall 3) Mehr als vier zahlen
- Das gleiche mit Fall 2
InformationsquelleAutor purucat

u have to consider 3 cases:
1. max 3 positive elements can be the first answer(say 10*20*70).
2. max positive elements multiplied by 2 most negative answers is another candidate(say20*-40*-60).
3.in case where all array elements are negative,3 elements with minimum negative magnitude is answer(-1*-2*-3 in [-1,-2,3,-4,-5]).

for simplicity of question we can merge 1st and 3rd case.
find 3 maximum elements of array, similarly find 2 minimum elements of array.
u will get 2 candidates. Print the maximum of those candidates.

C++ Code:
#include <iostream>
#include <limits.h>
using namespace std;

int main() 
{
    int n;  cin>>n;     int arr[n];     for(int a=0;a<n;a++)     cin>>arr[a];
    bool flag=0;
    int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
    int min1=INT_MAX,min2=INT_MAX;

    for(int a=0;a<n;a++)
    {
        if(arr[a]>max1)     {max3=max2;     max2=max1;      max1=arr[a];}
   else if(arr[a]>max2)     {max3=max2;     max2=arr[a];}
   else if(arr[a]>max3)     max3=arr[a];    flag=1;


        if(arr[a]<min1)     {min2=min1;     min1=arr[a];}
   else if(arr[a]<min2)     min2=arr[a];
    }    

    int prod1=INT_MIN,prod2=INT_MIN;
    if(max1>INT_MIN && max2>INT_MIN && max3>INT_MIN)    prod1=max1*max2*max3;
    if(max1>INT_MIN && min1<INT_MAX && min2<INT_MAX)    prod2=max1*min1*min2;

    cout<<max(prod1,prod2)<<endl;                                                
}

InformationsquelleAutor Gautam Malhotra

 //Here is a simple java program to find the maximum product of three numbers in  an array.

import java.util.*;
import java.lang.*;

class MOHAN_BERA
{
public static void main(String[] args)
{
    Scanner s = new Scanner(System.in);
        System.out.println("enter the lenth of array:");
        int num1=s.nextInt();
        int[] num2=new int[num1];
        System.out.println("enter the numbers of array:");
        for(int i=0;i<num1;i++)
        {
            num2[i]=s.nextInt();
        }
        Arrays.sort(num2);//sort the array

        long max1=num2[num1-1]*num2[num1-2]*num2[num1-3];//Three last numbers, can be three positive numbers
        long max2=num2[num1-1]*num2[0]*num2[1];//last numbers and first two numbers,can be first two negetive and last one positive numbers
        long max3=num2[0]*num2[1]*num2[2];//for all negetives numbers

        long max=max1;//max1 greatest
        if(max<max2 && max3<max2) //max2 greatest
        {
            max=max2;
        }
        else if(max<max3 && max2<max3)//max3 greatest
        {
            max=max3;
        }
        System.out.println(max);
 }
 }

InformationsquelleAutor Let's Learn Together

Sortieren Sie Das Array

Dann max werden entweder das Produkt der letzten 3 oder ersten 2(bei negativen zahlen) und die letzten.

 Arrays.sort(arr);
 int max1 = (arr[n - 1] * arr[n - 2] * arr[n - 3]);
 int max2 = (arr[0] * arr[1] * arr[n - 1]);
 System.out.println(max1 > max2 ? max1 : max2);

InformationsquelleAutor Sailee Renapurkar

in JavaScript

function largestProduct(ints) {
    ints.sort((a, b) => b - a);
    return ints[0] * ints[1] * ints[2];
}

InformationsquelleAutor Shanu T Thankachan

Sprache - C#

Greedy-Ansatz

Zeit Komplexität O(n)

 public static int GetHighestProductOfThree(int[] arrayOfInts)
        {

            if (arrayOfInts.Length < 3)
            {
                throw new ArgumentException("Array should be atleast 3 items", nameof(arrayOfInts));
            }

            int highest = Math.Max(arrayOfInts[0], arrayOfInts[1]);
            int lowest = Math.Min(arrayOfInts[0], arrayOfInts[1]);

            int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
            int lowestProductOf2 = arrayOfInts[0] * arrayOfInts[1];

            int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];

            for (int i = 2; i < arrayOfInts.Length; i++)
            {
                int current = arrayOfInts[i];
                highestProductOf3 = Math.Max(Math.Max(
                    highestProductOf3,
                    current * highestProductOf2),
                    current * lowestProductOf2);

                highestProductOf2 = Math.Max(Math.Max(
                    highestProductOf2,
                    current * highest),
                    current * lowest);

                lowestProductOf2 = Math.Min(Math.Min(
                    lowestProductOf2,
                    current * highest),
                    current * lowest);

                highest = Math.Max(highest, current);
                lowest = Math.Min(lowest, current);
            }

            return highestProductOf3;
        }

Dank interviewcake.com

Ausführliche Erklärung des Algorithmus

InformationsquelleAutor Code-EZ

-1

Können Sie mithilfe der eingebauten sort-Funktion von Javascript.Müssen vorsichtig sein, während der Suche nach max triplet Produkt, wie im Falle von array -ve-Nummern Produkt-Kombination die ersten 2 und die Letzte und bei allen +ve die letzten 3 Nummer Produkt führen.Sie können sich meine jsfiddle. Auch die Komplexität dieses Algorithmus ist O(nlogn)

var arr=[-10, 3, 5, 6, -20];
function maxTripletProduct(data)
{
  var sortedarr=data.sort(function(a,b){
  return a-b;
})
console.log(sortedarr);

let length=sortedarr.length;
let product1 = sortedarr[length-3]*sortedarr[length-2]*sortedarr[length-1]
let product2=sortedarr[0]*sortedarr[1]*sortedarr[length-1];
if(product2>product1)
  console.log(product2);
else
  console.log(product1);
}
maxTripletProduct(arr);

InformationsquelleAutor Avinash

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.