Array Summe bestimmen tipps?

[gotzi242]

Hallo ich wollte fragen ob jemand mir einen passenden code zeigen könnte wie man aus einem array die grösste zusammenhängende Summe bestimmen kann? 🙂 Danke

 

[Barista]

wie man aus einem array die grösste zusammenhängende Summe bestimmen kann

Was bedeutet "grösste zusammenhängende Summe"?

 

[gotzi242]

Was bedeutet "grösste zusammenhängende Summe"?

Sagen wir ich habe einen Array mit 10 Zahlen und ich vermute damit ist gefragt welche grösst mögliche Summe dabei entstehen kann

 

[Barista]

Sagen wir ich habe einen Array mit 10 Zahlen und ich vermute damit ist gefragt welche grösst mögliche Summe dabei entstehen kann

Es gibt nur eine Summe, diese ist damit gleichzeitig auch die grösste Summe, aber auch die kleinste Summe.

 

[mrBrown]

Es gibt nur eine Summe, diese ist damit gleichzeitig auch die grösste Summe, aber auch die kleinste Summe.

Maximum subarray problem - Wikipedia

en.wikipedia.org

 

[Barista]

Maximum subarray problem - Wikipedia

Davon war nicht die Rede.
Ich gehe davon aus, dass man schon die richtige Frage stellen muss, um die richtige Antwort zu bekommen.

 

[Barista]

Maximum subarray problem - Wikipedia

Wenn es effektiv sein soll, sicher etwas mit dynamischer Programmierung.

Anderenfalls kann man es auf folgende zwei Probleme herunterbrechen:

1. Alle möglichen zusammenhängenden Sub-Arrays ermitteln.

2. Das Sub-Array mit der höchsten Summe ermitteln.

Das Erste kann man mit zwei geschachtelten for-Schleifen erledigen.

Das Zweite sollte auch ein Anfänger hinbekommen.

 

[mihe7]

Nein, das geht in linearer Zeit mit einem Sweep.

 

[temi]

Sagen wir ich habe einen Array mit 10 Zahlen und ich vermute damit ist gefragt welche grösst mögliche Summe dabei entstehen kann

Da könnte man die größtmögliche Summe von zwei nebeneinander liegenden Zahlen vermuten.
Oder die größtmögliche Summe von zwei Zahlen, egal an welcher Stelle.
Oder ...

 

[mihe7]

Hm... mit "größte zusammenhängende Summe" ist doch relativ klar, was gemeint ist. Was soll denn mit "zusammenhängender Summe" in einem Array anderes als "Summe aufeinanderfolgender Elemente" gemeint sein?

 

[temi]

Hm... mit "größte zusammenhängende Summe" ist doch relativ klar, was gemeint ist. Was soll denn mit "zusammenhängender Summe" in einem Array anderes als "Summe aufeinanderfolgender Elemente" gemeint sein?

Jetzt wo du es sagst 😉

Wobei drei, vier oder alle Elemente auch zusammenhängend sind.

Ok, dann ein Tipp für die Ermittlung der größtmöglichen Summe zweier aufeinanderfolgender Elemente:

Für jedes Element im Array vom ersten bis zum vorletzten:

Ermittle die Summe aus aktuellem Element plus dem nachfolgenden Element.

Wenn die Summe größer ist als das bisherige Maximum, dann merke dir das neue Maximum.

 

[mihe7]

Wobei drei, vier oder alle Elemente auch zusammenhängend sind.

Ja, das ist auch so gemeint 🙂 Nicht nur zwei aufeinanderfolgende Elemente, es können alle sein, nur fünf etc.

 

[kneitzel]

Das mit einem beliebigen zusammenhängenden Teilarray kann Sinn machen. Es könnte ja auch negative Elemente geben...

Also sowas wie ein Array wie; 10, -25, 7, 8, -20, 9

Da wäre dann das Teilstück von 7 und 8 das Teilarray, dessen Summe am höchsten ist.

Also ohne Details der Aufgabe könnte man da schon einiges rein interpretieren ....

 

[gotzi242]

Das mit einem beliebigen zusammenhängenden Teilarray kann Sinn machen. Es könnte ja auch negative Elemente geben...

Also sowas wie ein Array wie; 10, -25, 7, 8, -20, 9

Da wäre dann das Teilstück von 7 und 8 das Teilarray, dessen Summe am höchsten ist.

Also ohne Details der Aufgabe könnte man da schon einiges rein interpretieren ....

Genau so ist das gemeint. Tut mir Leid für das falsche beschreiben

 

[kneitzel]

Hast Du Dir denn zur Lösung mal paar Gedanken gemacht? Wie würdest Du da vorgehen? Also vergiss Java. Du bekommt einen Zettel mit Zahlen und sollst die Zahlenreihe mit der größten Summe bestimmen. Was kann man da z.B. machen?