Maximum Subarray Problem

21.02.2012, 15:43

rawfood

Maximum Subarray Problem

Hallo,

Ich arbeite mich gerade durch ein Buch über Algorithmen und Datenstrukturen. Es geht um Algorithmen für ein Problem mit unterschiedlicher Laufzeit und Komplexität. Beim Maximum Subarray Problem hat man eine Folge von Zahlen gegeben. Gesucht ist die größte Teilmenge dieser Folge.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

#include <iostream>
using namespace std;
int max(int a, int b)
{
if (a>b) return a;
else return b;
}
int main()
{
int summe;
int maxtsumme=0;
int feld[] ={3,4,-2,6,-4,2,1,9,-3,-1}; 
for (int u=0;u<(sizeof(feld)/sizeof(int));u++)
{
for (int o=u; o<(sizeof(feld)/sizeof(int));o++)
{
summe=0;
for (int i=u; i<=o;i++)
{
//cout << "i:" << i << "o: "<< o << "u: "<< u << "\n";
summe=summe+feld[i];
}
maxtsumme=max(summe, maxtsumme);
cout << "Die Summe von o: " << o << "ist " << summe <<"\n";
}
}
cout << "Die Summe ist " <<  maxtsumme << "\n";
}

Das ist der naive Ansatz aus dem Buch. Also im Buch ist der Algo in Pseudocode eingegeben. Aus Interesse habe ich den Algo in C übersetzt und ausgeführt.

Jetzt wird der nächst beste Algorithmus zu dem Problem durch das Teile und Herrsche Prinzip realisiert. Sprich die Folge wird in zwei annähernd gleich große Teilfolgen zerlegt. Entweder befindet sich die größte Teilmenge in der linken oder rechten Folge, oder ebend im Bereich des "Schnittpunktes" der Menge. Die maximale Summe vom der linken Menge bis zum rechten Rand heißt linke Randmaximum, und die rechte Menge vom rechten Rand bis zum Ende ebend rechtes Randmaximum. Das linke Randmaximum läßt sich in Großtheta(r-l) Schritte berechnen für eine Folge X[l],...,X[r] ganzer Zahlen.

angegeben ist folgender Pseudocode:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	lmax:=0; summe:=0; for i:=l to r do begin summe:=summe+X[i]; lmax:=max(lmax, summe); end

Jetzt habe ich zum Verständnis folgende Folge genommen : {3,4,-2,6,-4,2,1,9,-3,-1}

Und habe eine Tabelle gebildet und lmax bestimmen wollen:
Die Folge wird in die Menge {3,4,-2,6,-4} gesplittet, bzw der Index der For Schleife wird von Element 1 bis Element n/2 gesetzt.

i l summe lmax
1 5 3 3 (summe=0+3)
2 5 7 7 (summe=3+4)
3 5 5 7 (summe=7+(-2))
4 5 11 11
5 5 7 11

So und hier habe ich ein Problem. Lmax ist doch am Ende 11.

Rmax ist jetzt 12.

i l summe rmax
6 10 2 2
7 10 3 3
8 10 12 12
9 10 9 12
10 10 8 12

Jetzt wird beim Pseudocode aber folgendes angegeben :

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

Algorithmus maxtsum (X );
fliefert eine maximale Teilsumme der Folge X ganzer Zahleng
begin
if X enthält nur ein Element a
then
if a > 0
then maxtsum := a
else maxtsum := 0
else
begin
fDivide:g
teile X in eine linke und eine rechte Teilfolge A und B
annähernd gleicher Größe;
fConquer:g
maxtinA := maxtsum(A);
maxtinB := maxtsum(B);
bestimme das rechte Randmaximum rmax(A) der
linken Teilfolge A;
bestimme das linke Randmaximum lmax(B) der
rechten Teilfolge B;
fMerge:g
maxtsum := max(maxtinA, maxtinB, rmax(A) + lmax(B))
end
end fmaxtsumg

Und im Pseudocode steht nun aber maxtsum:=max(maxtinA, maxtinB, rmax(A)+lmax(B))
mein lmax ist 11 und rmax ist 12....und die Summe wäre dann 23. Im anderen Algo hab ich aber 19 ermittelt...

Ich sehe das Problem im letzten Schritt bei lmax .... 5 5 7 11
Die eigentlich Endsumme 7 + rmax = 12, wären 19....

Ich hoffe das ihr bishierher schon meinen Denkfehler gefunden habt, und mir helfen könnt.

Lg
rf

21.02.2012, 16:37

Auf diesen Beitrag antworten »

rawfood

Ich musste den Post kurzerhand abbrechen, weil ich Weg musste. Mein Problem ist, was ist mit Randmaximum gemeint?

Lg
Rf

Neue Frage »

Antworten »

Maximum Subarray Problem

Verwandte Themen