Methoden Teil-Array mit Maximalwert bestimmen

[Daisoke]

Hallo zusammen.
Bin noch relativ neu dabei.

Ich habe folgendes Problem:

Ich möchte aus einem Array die maximale Summe eines Teil-Arrays ermitteln.

Beispiel: Bei einem Array a={1,2,3,4,-100,1,2,3,4,5,6} sollte das Ergebnis 21 sein.

Ich sitze lange an diesem Problem aber ich habe gerade keinen Anhaltspunkt bei dem Verfahren mithilfe einer doppelten Schleife.

Aktuell sieht mein Verfahren so aus:

[/B]
public static int myArray(int[] s) {
        int max = s[0];
        for (int i = 0; i <= s.length - 1; i++) {
            for (int j = i; j < s.length - 1; j++) {
                int total = s[i];
                if (total >= max) {
                    total = total + s[j];
                }
                max = total;
            }
        }
        return max;
    }
[B]

Hier berechne ich den Wert 10.
Ich bitte euch um einen kleinen Hinweis, wie ich das Problem beheben könnte.

 

[Jw456]

wieso doppelte Schleife?

du gehst das Array einmal durch und addierst die werte
du willst doch die Quersumme haben wie würdest du das auf Papier oder Kopf machen

 

[Jw456]

Frage womit wird denn dein Array geteilt?
du willst die Quersumme doch erst ab einer ganz bestimmten Stelle wie stellst du das fest ?

 

[Daisoke]

wieso doppelte Schleife?

du gehst das Array einmal durch und addierst die werte
du willst doch die Quersumme haben wie würdest du das auf Papier oder Kopf machen

Das ist von der Aufgabenstellung so vorgegeben. Ich hätte es eigentlich auch ganz anders gemacht. Hier stecke ich leider fest.

 

[Jw456]

 total = total + s[j];
// du willst  mit max addiren.
und wenn die -100 kommt must du max wider auf anfang setzen

 

[KonradN]

Der erste Schritt ist immer, dass Du das Vorgehen, den Algorithmus, genau formulierst.

Du musst alle Teil-Arrays ermitteln. Das kannst Du mit zwei Schleifen machen. Aber die Grenzen musst Du noch einmal betrachten!

Also nehmen wir einmal das Array [1, 2, 3]
Alle möglichen Teilarrays wären dann erst nur [1], [1,2], [1,2,3]
Dann geht es mit der 2 los - aber welche Teilarrays betrachtest Du dann noch?

Wenn Du alle Teil-Arrays bilden kannst (mit zwei Schleifen), dann wäre die Frage, in wie weit Du daraus jetzt die Summen erstellen kannst. Das Ginge zur Not auch wieder mit einer einfachen Schleife.

Du kannst Dir das aber ggf. auf einem Zettel noch etwas überlegen - wenn Du nur die Teilarrays bildest mit dem [1], [1,2], [1,2,3] - kannst Du da ggf. schon direkt die Summe bilden bei jedem Schritt?

 

[Jw456]

Ok

Dann Bilde doch in der inneren Schleife immer die Quersumme.
Am ende prüfst du erst ob das total Ergebnis grösser als max ist .
Ist es das merkst du es dir setzt das max, wenn nicht mache weiter.

 

[Jw456]

for (int i = 0; i < s.length; i++) {
            int total = s[i];
            for (int j = i + 1; j < s.length; j++) {
                total = total + s[j];
            }
    ...

 

[Jw456]

Der erste Schritt ist immer, dass Du das Vorgehen, den Algorithmus, genau formulierst.

Du musst alle Teil-Arrays ermitteln. Das kannst Du mit zwei Schleifen machen. Aber die Grenzen musst Du noch einmal betrachten!

Also nehmen wir einmal das Array [1, 2, 3]
Alle möglichen Teilarrays wären dann erst nur [1], [1,2], [1,2,3]
Dann geht es mit der 2 los - aber welche Teilarrays betrachtest Du dann noch?

Wenn Du alle Teil-Arrays bilden kannst (mit zwei Schleifen), dann wäre die Frage, in wie weit Du daraus jetzt die Summen erstellen kannst. Das Ginge zur Not auch wieder mit einer einfachen Schleife.

Du kannst Dir das aber ggf. auf einem Zettel noch etwas überlegen - wenn Du nur die Teilarrays bildest mit dem [1], [1,2], [1,2,3] - kannst Du da ggf. schon direkt die Summe bilden bei jedem Schritt?

Die Teil Bereiche die er sucht sind
1,2,3
2,3
3
Um bei deinem Beispiel zu bleiben.

 

[KonradN]

Wo braucht man bitte eine Quersumme bei der Aufgabe?

Und in welcher Reihenfolge er die Teilarrays bildet, ist egal. Wobei die Reihenfolge, die ich genannt habe schlicht den Vorteil hat, dass man beim Erstellen der Teilarrays auch direkt die Summe bilden kann so dass eben die 2 verschachtelten Schleifen ausreichen.

 

[Jw456]

Der TE will das mit zwei Schleifen haben, und genau das haben ich auch erklärt.
Das macht auch der Code Ausschnitt den ich gegeben habe.
Gut du störst dich wider an der Begrifflichkeit (Quersumme) dann sagen wir er addiert in der inneren Schleife die Zahlen-Kolonne, und genau das mache ich auch. Und will der TE auch machen.
Und das größte Ergebnis soll er sich merken. Das habe ich natürlich noch nicht gemacht.

int[] a = {1,2,3,4,-100,1,2,3,4,5,6};

1+2+3+4+(-100)+1+2+3+4+5+6 = -69
2+3+4+(-100)+1+2+3+4+5+6 = -70
3+4+(-100)+1+2+3+4+5+6 = -72
4+(-100)+1+2+3+4+5+6 = -75
-100+1+2+3+4+5+6 = -79
1+2+3+4+5+6 = 21
2+3+4+5+6 = 20
3+4+5+6 = 18
4+5+6 = 15
5+6 = 11
6 = 6

Bei dir würde es so anfangen.

1=1
1+2 = 3
1+2+3 = 6
1+2+3+4 = 10
1+2+3+4+(-100) = -90
1+2+3+4+(-100)+1 = -89
1+2+3+4+(-100)+1+2 = -87
1+2+3+4+(-100)+1+2+3 = -84
1+2+3+4+(-100)+1+2+3+4+5 = -75
1+2+3+4+(-100)+1+2+3+4+5+6 = -69

Ja du sagst danach geht es mit der 2 weiter .
Also

2 = 2
2+3 = 5
2+3+4 = 9
2+3+4+(-100) = -91
....

Ja auch du würdest zu

1+2+3+4+5+6 = 21

Kommen

 

[Meniskusschaden]

Wo braucht man bitte eine Quersumme bei der Aufgabe?

Man könnte die (Teil-)Array-Elemente ja als die Ziffern einer Zahl im 4294967296er-System betrachten.

 

[KonradN]

a) Quersumme ist ein klar definierter Begriff. Wirf nicht mit Begriffen um Dich, wenn Du die Bedeutung nicht kennst. Und wenn man Dich auf sowas hinweist, dann ist eine Reaktion a.la. "Wenn Du Dich daran störst" gelinde gesagt: Dumm. Eigentlich sollte es in Deinem Interesse sein, dass Du Begriffe korrekt benutzt. Hast Du denn einmal den Begriff Quersumme nachgeschaut? Z.B. auf Wikipedia?

b) Deine Beiträge zu dem Algorithmus sind teilweise sehr verwirrend. Wenn Du bei dem größten Teilarray anfängst, dann brauchst Du vermutlich 3 Schleifen: Eine für den Anfang, eine für das Ende und eine zur Berechnung der Summe. Ich gewinne daher den Eindruck, dass Du den Algorithmus noch nicht wirklich durchblickt hast. Hast Du das denn einmal für Dich wirklich gelöst? Hast Du einen fertigen Code? Das würde Dir gewisse Sicherheit geben, wenn Du so auftrittst.

Man könnte die (Teil-)Array-Elemente ja als die Ziffern einer Zahl im 4294967296er-System betrachten.

Ja, nur ich fürchte, dass dies dann bei Elementen > 9 oder < -9 sowie bei negativen Zahlen zu nicht wirklich brauchbaren Ergebnissen führen würde.

 

[Jw456]

b) Deine Beiträge zu dem Algorithmus sind teilweise sehr verwirrend. Wenn Du bei dem größten Teilarray anfängst, dann brauchst Du vermutlich 3 Schleifen: Eine für den Anfang, eine für das Ende und eine zur Berechnung der Summe. Ich gewinne daher den Eindruck, dass Du den Algorithmus noch nicht wirklich durchblickt hast. Hast Du das denn einmal für Dich wirklich gelöst? Hast Du einen fertigen Code? Das würde Dir gewisse Sicherheit geben, wenn Du so auftrittst.

b.)
Du hast die vorgehensweise in Post #6 beschrieben und da würdest du 3 Schleifen brauchen die dritte zum Addieren .

Also nehmen wir einmal das Array [1, 2, 3]
Alle möglichen Teilarrays wären dann erst nur [1], [1,2], [1,2,3]
Dann geht es mit der 2 los - aber welche Teilarrays betrachtest Du dann noch?

 

[KonradN]

b.)
Du hast die vorgehensweise in Post #6 beschrieben und da würdest du 3 Schleifen brauchen die dritte zum Addieren .

Das ist jetzt nicht Dein Ernst, oder? Sorry, aber hast du den Beitrag ganz gelesen? Und verstanden? Der letzte Abschnitt weist darauf hin, dass man den Schritt der Summenberechnung direkt in der zweiten Schleife abhanden kann.

Vielleicht willst di das, das ich dem TE geraten habe, selbst erst einmal nachvollziehen?

 

[Meniskusschaden]

Du hast die vorgehensweise in Post #6 beschrieben und da würdest du 3 Schleifen brauchen die dritte zum Addieren .

Er hat - wohl aus didaktischen Gründen - geschrieben, dass es "zur Not" auch mit drei Schleifen ginge und den Gedankenanstoss zur direkten Summenbildung gleich mitgeliefert. Das sollte der TE aber selbst entdecken.

Zwischen euren Lösungsansätzen kann ich im Moment übrigens keinen wesentlichen Unterschied feststellen.

 

[Jw456]

Das ist jetzt nicht Dein Ernst, oder? Sorry, aber hast du den Beitrag ganz gelesen? Und verstanden? Der letzte Abschnitt weist darauf hin, dass man den Schritt der Summenberechnung direkt in der zweiten Schleife abhanden kann.

Vielleicht willst di das, das ich dem TE geraten habe, selbst erst einmal nachvollziehen?

Hast du dir meinen Post #8
Angesehen und angesehen das ich in der inneren Schleife addiere.
ich wollte natürlich nicht denn kompetten Code geben

 

[KonradN]

Zwischen euren Lösungsansätzen kann ich im Moment übrigens keinen wesentlichen Unterschied feststellen.

Mich regt es einfach massiv auf, dass da ständig Kommentare zu mir kommen, die nichts beitragen. Was hilft denn das #9 weiter? Ich erkläre ein Vorgehen. Und erläutere dieses Vorgehen an Hand eine Beispiels. Das Vorgehen natürlich erst einmal ganz nach Schema F. Das sollte ja jedem, der meine Beiträge kennt, bekannt sein. Und dann erst den Hinweis auf eine mögliche Optimierung.

Und das Vorgehen richtet sich dabei relativ stark, nach dem, was der TE schon hat. Und da hat er zwei Schleifen die den Zähler immer erhöhen.

Aber wer erkläre ich, wieso ich so antworte, wie ich antworte? Die, die es interessieren sollte und die vielleicht auch vor einer Antwort etwas mehr nachdenken sollten, was für den TE Sinn machen könnte, wird es nicht weiter interessieren.

Aber - um es einfach abzuschließen damit ich aus dem Thread dann raus bin:

Eine Lösung kann so aussehen:

        int [] values = { -100, 4, -3, 4, -5};

        int max = values[0];

        for (int startIndex = 0; startIndex < values.length; startIndex++) {
            int summe = 0;
            for (int endIndex = startIndex; endIndex < values.length; endIndex++) {
                summe += values[endIndex];
                if (max < summe) max = summe;
            }
        }

Beim setzen des endIndex wird der entsprechende Wert zur Summe hinzu addiert. Und immer, wenn man ein neuen Startpunkt hat, dann wird bei 0 angefangen.

Also wenn man das Array [1, 2, 3] hat, dann gehe ich ja von Hand auch nicht anders vor:
Ich betrachte
Summe erst 0.
dann [1] -> 0 + 1 = 1
dann [1, 2] -> 1 + 2 = 3
dann [1, 2, 3] -> 3 +3 = 6
Es wird also immer das vorherige Summen-Ergebnis weiter genommen.

Das Schema F hätte zu einem Ergebnis geführt, das so ausgesehen hätte:

        int max = values[0];

        for (int startIndex = 0; startIndex < values.length; startIndex++) {
            for (int endIndex = startIndex; endIndex < values.length; endIndex++) {
                int summe = berechneSumme(values, startIndex, endIndex);
                if (max < summe) max = summe;
            }
        }

 

[Jw456]

In Code geschrieben machst du genau das gleiche wie ich.
Ja du hast sinnvoller Variablennamen wollte dem TE seinen Code nicht komplett verändern.

 

[KonradN]

Es ging mir nie um Deinen Code sondern um Deine Aussagen im Text.

Wie ist dein #9 zu verstehen? Du gehst die Teilarrays ja ebenso in der anderen Reihenfolge an. Aber ich will das nicht weiter diskutieren.

 

[Jw456]

Ich habe deine Aussage so verstanden das du
Array [1, 2, 3]

Das du vom außen betrachtet

{ 0+1 rechnest
Zweiter Durchlauf
1+2
Dritter
1+2+ 3 } // innere Schleife


Dann mit deiner 2 weiter machst

{ 0+2 rechnest
Zweiter Durchlauf
2+3
} // innere Schleife

Ich finde es für mich eine verwirrende Schreibweise
>Also nehmen wir einmal das Array [1, 2, 3]
>Alle möglichen Teilarrays wären dann erst nur [1], [1,2], [1,2,3]

Ich sehe hier 0+1 / 1+2 / 1+2+3 von außen im ganzen gesehen.

 

[Jw456]

Bei deinem Code könnte man sogar wenn das zwischen Ergebnis summe keiner als max ist , die innere Schleife auch abbrechen verlassen.


Gut dann habe ich deine Algorithmus Erklärung falsch verstanden und wir haben an einander vorbei geredet.
Aber auch du hast nicht versucht meine sichtweise zu verstehen.

 

[KonradN]

Bei deinem Code könnte man sogar wenn das zwischen Ergebnis summe keiner als max ist , die innere Schleife auch abbrechen verlassen.

Nein, das geht nicht. Denn natürlich kann noch ein größerer Wert kommen.

Wenn die Summe negativ ist, dann sollte man abbrechen können, aber nur ein Summe kleiner als max reicht nicht aus.

 

[Jw456]

ich meinte negativ sorry