Signifikante Array-Indizes finden

[Affe Hornmann]

Moin,

Bei mir klemmt's gerade an folgendem Problem:

Ich habe ein langes int-Array - ein Beispiel ist unten.
Nun suche ich eine Möglichkeit, den Bereich (oder die Mitte des Bereichs) im Array zu finden, in dem die Zahlenfolge >0 mit der größten Summe liegt.

0 0 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 
2 2 1 2 1 2 2 2 2 2 2 2 1 2 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 
0 0 0 1 1 1 1 0 0 1 0 0 0 1 2 1 1 1 0 1 1 2 1 1 2 2 2 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Im Beispiel will ich also den Bereich "1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 2 2 1 2 1 2 2 2 2 2 2 2 1 2 2 2 1 1" finden.

Wenn ich es heuristisch über ein reines Maximum versuche, erhalte ich zu viele falsche Ergebnisse - im Beispiel wäre das ja die "4".

Idealerweise sollte der Ansatz auf O(n) optimierbar sein, während ich das Array berechne. (Das ist auch der Punkt an dem es wirklich hakt)

Viel Spaß 😀,
Affe

 

[timbeau]

Die größte Summe bedeutet was genau? In deinem Beispiel-Array werden also Zahlenpakete durch "0"en getrennt?! Und du willst das Paket finden, bei dem die einzelnen Zahlen addiert, die größte Summe ergeben?

Also 00011100 < 00022000?!

Dann würde ich über das Array laufen, und sobald int != 0 anfangen zu zählen bis int == 0. Maximum speichern und weiterzählen.

 

[XHelp]

Wieso solltest du da die 4 bekommen? Die Summe von dem Batzen 1 und 2 ist wohl offensichtlich größer als 4.
Darüber hinaus: "1111" und "4": was ist denn signifikanter?
Was O(n) betrifft: du musst ja nur einmal durch das ganze Array laufen und die Zahlen aufaddieren - das ist O(n)

 

[Affe Hornmann]

Also, ich habe meine Angst vor der Aufgabe überwunden, und.... es hinbekommen 🙂
Anbei ein Codesnippet.

int start = 0, sum = 0;
int maxstart = 0, maxend = 0, maxsum = 0;
for (int x = 1; x <= length - 1; x++) {
	array[x] = fuelleArray(x);
	if(array[x] == 0) { 
		if(sum > maxsum) {
			maxsum = sum; 
			maxstart = start;
			maxend = y;
		}
		sum = 0;
		start = y;
	} else sum += array[y];
}
System.out.println("start=" + maxstart + " end=" + maxend);

Affe