C# Problem mit Randposition für Max Teilsumme

Suprimos · 28. April 2011

Hallo,

ich soll einen Algo programmieren der die maximale Teilsumme für ein beliebiges Subarray berechnet.
Den algo habe ich bereits gefunden und implementiert. Problem ist derzeit, ich soll zusätzlich zur maximalen Teilsumme noch die Randpositionen ausgeben.
Ich habe es bisher nur geschafft die rechte Position auszugeben, allerdings weiß ich nicht wie ich die linke ausgeben soll.
Vielleicht habt ihr einen Tipp für mich.
Hier mein Code bisher:

public static int Teilsum (int [] array)
{

int max_so_far = 0;
int max_ending_here = 0;
int i;
for(i = 0; i < array.Length; i++)
{
max_ending_here = max_ending_here + array;
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
rechts=i;
}
return max_so_far;
}

PS: rechts, links würde ich erstmal global machen...

Ergänzung (28. April 2011)

hat keiner eine idee?...

Ergänzung (28. April 2011)

also es handelt sich hierbei um den kadane algo für max subarray...

lynxx · 28. April 2011

Also rechts=i; kann schonmal nicht sein, dann kannst Du auch gleich rechts = array.Length; ausserhalb der Schleife schreiben.

Wie sieht so ein Array etwa aus, so in der Art vielleicht?
int [] array = { 0,0,10,11,12,13,-240,4,5,90,183,-540,-330 };

Suprimos · 28. April 2011

also meiner meinung nach passt rechts=i
da ich mir mit rechts sozusagen den schritt merke, in dem max_so_far das letzte mal geupdatet wurde...

bsp:

{-2, -3, 4, -1, -2, 1, 5, -3}

Ergebnis hier = 7

max_so_far = max_ending_here = 0

for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
Set max_ending_here = 0 because max_ending_here < 0

for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
Set max_ending_here = 0 because max_ending_here < 0

for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_so_far is updated to 4 because max_ending_here greater than max_so_far which was 0 till now

for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3

for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1

for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2

for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
max_so_far is updated to 7 because max_ending_here is greater than max_so_far

for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4

lynxx · 28. April 2011

Suprimos schrieb:
also meiner meinung nach passt rechts=i
da ich mir mit rechts sozusagen den schritt merke, in dem max_so_far das letzte mal geupdatet wurde...

bsp:

{-2, -3, 4, -1, -2, 1, 5, -3}

Ergebnis hier = 7

Dann müsste es so aussehen: (geschweifte Klammern um max_so_far-Block & rechts=i )

Code:

public static int Teilsum (int [] array)
{
	int max_so_far = 0;
	int max_ending_here = 0;
	int i;
	links = 0;
	for(i = 0; i < array.Length; i++)
	{
		max_ending_here = max_ending_here + array[i];
		
		if(max_ending_here < 0) {
			max_ending_here = 0;
			links = i;
		}
		
		if(max_so_far < max_ending_here)
		{
			max_so_far = max_ending_here;
			rechts = i;
		}
	}
	return max_so_far;
}

max_so_far wird doch bei -3 als letztem Element nicht mehr aktualisiert ("geupdatet"

).
und links ist ab da wo max_ending_here = 0; gesetzt wird.

Suprimos · 28. April 2011

klappt leider nicht...
er gibt aus:
max_so_far = 7 korrekt
links=1 falsch
rechts=6 korrent

{-2,-3,4,-1,-2,1,5,-3}
die maximale teilsumme ist hier:

4+(-1)+(-2)+1+5 = 7
also von arrayposition 3 bis 6 (da arrayindex mit 0 beginnt)

würde ein links=i+1 abhilfe schaffen?...
ich muss es mal testen

EDIT:
links=i+1 scheint zu klappen...
habe mal eben 4 arrays getestet...und es hilft

kann zwar nicht erklären warum, aber hautsache es klappt erstmal..
danke

lynxx · 28. April 2011

huch, ja richtig .. links ist der erste wo max_ending_here nicht 0 ist ..

Code:

		if(max_ending_here < 0) {
			max_ending_here = 0;
			links = i+1;
		}

Suprimos · 28. April 2011

vielen vielen dank nochmal

lynxx · 28. April 2011

Denke mal da können auch nullen im Array sein, dann ist das besser:

Code:

		if (max_ending_here <= 0) {

Suprimos · 28. April 2011

hab beim weiteren testen doch noch fehler gefunden

sum=6
links=5
rechts=0
{6,-11,-1,-7,-9,0}

oder:

sum=11
links=5
rechts=1
{1,10,-14,-5,-12,0}

oder:

sum=0
links=2
rechts=0
{-2,-9,0}

lynxx · 28. April 2011

Probier mal:

Code:

public static int Teilsum (int [] array)
{
	int max_so_far = 0;
	int max_ending_here = 0;
	int i;
	int linkstemp = 0;
	links = 0;
	for(i = 0; i < array.Length; i++)
	{
		max_ending_here = max_ending_here + array[i];

		if (max_ending_here <= 0) {
			max_ending_here = 0;
			linkstemp = i;
		}
		
		if (max_so_far < max_ending_here) {
			max_so_far = max_ending_here;
			links = linkstemp;
			rechts = i;
		}
	}
	return max_so_far;
}

Suprimos · 28. April 2011

klappt leider auch nicht mit den selben arrays

1668mib · 28. April 2011

Mehr oder wengier 1:1 aus dem Wiki-Pseudo-Code übersetzt... ka ob es funktioniert, sieht im Großen und Ganzen auch sehr ähnlich aus wie deines - wobei deine Initialisierung für die Summe am Ende falsch ist... muss z.B. Int32.MinValue sein... (=> minus unendlich sozusagen)

Code:

class Program
    {
        static void Main(string[] args)
        {
            int[] array = { 0, 0, 10, 11, 12, 13, -240, 4, 5, 90, 183, -540, -330 };

            ResultClass result = maxSum(array);

            Console.WriteLine("max: " + result.sum);
            Console.WriteLine("startIndex: " + result.startIndex);
            Console.WriteLine("endIndex: " + result.endIndex);
            Console.ReadLine();
        }

        public static ResultClass maxSum(int[] array) {
            int maxSum = Int32.MinValue;
            int maxStartIndex = 0;
            int maxEndIndex = 0;

            int currentMaxSum = 0;
            int currentStartIndex = 0;

            for (int currentEndIndex = 0; currentEndIndex < array.Length; currentEndIndex++) {
                currentMaxSum = currentMaxSum + array[currentEndIndex];

                if (currentMaxSum > maxSum) {
                    maxSum = currentMaxSum;
                    maxStartIndex = currentStartIndex; 
                    maxEndIndex = currentEndIndex;
                }

                if (currentMaxSum < 0) {
                    currentMaxSum = 0;
                    currentStartIndex = currentEndIndex + 1;
                }
            }

            return new ResultClass(maxSum, maxStartIndex, maxEndIndex);
        }
    }

    class ResultClass
    {
        public int sum;
        public int startIndex;
        public int endIndex;

        public ResultClass(int maxSum, int maxStartIndex, int maxEndIndex) {
            this.sum = maxSum;
            this.startIndex = maxStartIndex;
            this.endIndex = maxEndIndex;
        }
    }

Edit2: Ok, scheint jetzt zu funktionieren...

Edit3: Also bei mir funktionieren auch die anderen geposteten Methoden... ich zweifel langsam an dem anderen Code in deinem Test-Programm....

Suprimos · 28. April 2011

boah...der is ja mal echt gut
und er klappt auch tip top...vielen vielen dank !
welchen wiki pseudo hast du genommen ?

1668mib · 28. April 2011

von hier http://en.wikipedia.org/wiki/Maximum_subarray_problem
aber wirklich andere Ergebnisse bekomme ich wie gesagt nicht wie du...
Ich glaube bei dir könnte ein Problem außerhalb der Methode sein...

Suprimos · 28. April 2011

was meinst du mit wirklich andere ergebnisse?

1668mib · 28. April 2011

Sorry doof formuliert... besser gesagt:
Mit den vorher geposteten Methoden erhielt ich aber die selben Ergebnisse, wie mit meinem Code. Deshalb denke ich, dass der Fehler bei dir wohl irgendwo anders lag...

Ist auch nicht gut, "links" und "rechts" als Rückgabewerte irgendwo anders definiert zu haben... ein Weg ist mein Ansatz mit (ausbaufähiger) Ergebnisklasse, andere Möglichkeit wären auch Ausgabe-Parameter...

also in der Art

Code:

public static int MaxSum(int[] array, out int startIndex, out int endIndex)

Suche

C# Problem mit Randposition für Max Teilsumme

Suprimos

Lieutenant

lynxx

Lt. Junior Grade

Suprimos

Lieutenant

lynxx

Lt. Junior Grade

Suprimos

Lieutenant

lynxx

Lt. Junior Grade

Suprimos

Lieutenant

lynxx

Lt. Junior Grade

Suprimos

Lieutenant

lynxx

Lt. Junior Grade

Suprimos

Lieutenant

1668mib

Gast

Suprimos

Lieutenant

1668mib

Gast

Suprimos

Lieutenant

1668mib

Gast

Ähnliche Themen