SubSquence

L

Lukases2

Aktives Mitglied
Hallo,

ich soll eine Methode implementieren, die die Teilfolge maximaler Summe anhand des folgenden Algorithmus berechnet:

Java: 
/* Initialisierung */
glob max <-  0
suffix max <-  0
l <- 1; r <- 0
sl <- 1; m <- 0
/* Ende der Initialisierung */

while m < n do
    m <- m + 1
        if a[m] + suffix max > glob max then
            suffix max   am + suffix max
            glob max <- suffix max
            l <- sl; r <- m
        else if a[m] + suffix max >= 0 then
            suffix max <- a[m] + suffix max
        else
            suffix max <- 0
            sl <- m + 1
        endif
    endif
endwhile
Die Folge ist F = {a[1], ... , a[n]}, a[1] != 0, n > 0
Nachbedingung: F(l,r) ist eine zusammenhängende Teilfolge maximaler Summe von F.

Gegeben ist folgende Java-Datei:
(Müsst ihr euch jetzt nicht so genau anschauen. Sie gibt die richtigen Lösungen an und sagt, ob meine Methode richtig rechnet.)
Java: 
public class MaxSubSeq {
	public static final class SubSequence {
		// Anfangsindex der Teilfolge
		final int start;
		// Länge der Teilfolge
		final int length;
		// Summe der Teilfolge
		final int sum;

		public SubSequence(int start, int length, int sum) {
			this.start = start;
			this.length = length;
			this.sum = sum;
		}

		@Override public boolean equals(Object object) {
			if(!(object instanceof SubSequence))
				return false;
			SubSequence other = (SubSequence)object;
			return start == other.start
					&& length == other.length
					&& sum == other.sum;
		}
	};

	static SubSequence optimalMaxSubSequence(int[] sequence) {
		// bitte implementieren Sie diese Methode!
		// geben Sie ein Objekt vom Typ SubSequence zurück,
		// das die maximale Teilfolge beschreibt.
		return new SubSequence(0, 0, 0);
	}

	public static SubSequence naiveMaxSubSequence(int[] sequence) {
		int global_start = 0, global_length = 0, global_sum = 0;

		for(int len = 1; len <= sequence.length; len++) {
			for(int i = 0; i < sequence.length - len + 1; i++) {
				int sum = 0;
				for(int j = 0; j < len; j++)
					sum += sequence[i + j];

				if(sum > global_sum) {
					global_start = i;
					global_length = len;
					global_sum = sum;
				}
			}
		}

		return new SubSequence(global_start, global_length, global_sum);
	}

	public static void main(String[] args) {
		int seq_length = 10;

		Random random = new Random();
		
		int num_trails = 10;
		int range = 20;

		for(int i = 0; i < num_trails; i++) {
			int[] sequence = new int[seq_length];
			for(int j = 0; j < seq_length; j++) {
				int abs = random.nextInt(range);
				sequence[j] = (random.nextBoolean() ? -abs : abs);
			}
			
			System.out.println(Arrays.toString(sequence));
			SubSequence max = optimalMaxSubSequence(sequence);
			System.out.println("    optimalMaxSubSequence() returned (start: " + max.start + ", length: " + max.length
					+ ", sum: " + max.sum + ")");
			
			SubSequence correct = naiveMaxSubSequence(sequence);
			if(max.equals(correct)) {
				System.out.println("    Correct!");
			}else{
				System.out.println("    Error! (start: " + correct.start + ", length: " + correct.length
						+ ", sum: " + correct.sum + ") is maximal!");
			}
		}
	}
}

Die von mir bereits umgesetzt Methode sieht so aus:
Java: 
static SubSequence optimalMaxSubSequence(int[] sequence) {
		
		/* Initialisierung */
		int glob_max = 0;
		int suffix_max = 0;
		int l = 1, r = 0;
		int sl = 1, m = 0;
		/* Ende Intitalisierung */

		while (m < sequence.length) {
			m += 1;
			for (int i = 0; i < sequence.length - 1; i++) {
				if(sequence[i] + suffix_max > glob_max){
					suffix_max += sequence[i];
					glob_max = suffix_max;
					l = sl;
					r = m;
				}
				else if(sequence[i] + suffix_max >= 0){
					suffix_max += sequence[i];
				}
				else{
					suffix_max = 0;
					sl = m+1;
				}
			}
		}
		return new SubSequence(0, 0, 0);
	}

Mein Problem
Ich weiß nicht, was ich in der Methode zurück geben soll. Den Pseudocode in Java zu verfassen war ja ziemlich einfach, aber ich verstehe nicht, was es mit dem Typ SubSequence auf sich hat. Ich vermute, dass an der Stelle
Java: 
return new SubSequence(0, 0, 0);
die Werte
Java: 
return new SubSequence(/*start, length, sum*/);
eingesetzt werden sollen. Wenn ich aber zum Beispiel
Java: 
return new SubSequence(l, r, glob_max);
einsetze, komme ich auf die falschen Ergebnisse.
Wie kann ich das umsetzen? Generell ist es das erste Mal, dass ich mit solchen selber erzeugten Datentypen arbeiten soll, deswegen fehlt mir auf jeden Fall Erfahrung damit.
 
Zuletzt bearbeitet:
L

Lukases2

Aktives Mitglied
Update
Ich habe die Methode ein wenig modifiziert, weil ich erkannt habe, dass m ja der Laufindex der Schleife sein soll. Ich hatte im ersten Beitrag also quasi zwei Schleifen laufen lassen. Die Methode sieht jetzt so aus:

Java: 
static SubSequence optimalMaxSubSequence(int[] sequence) {
		
		/* Initialisierung */
		int glob_max = 0;
		int suffix_max = 0;
		int l = 1, r = 0;
		int sl = 1;
		/* Ende Intitalisierung */

		for(int i = 0; i < sequence.length; i++){
			if(sequence[i] + suffix_max > glob_max){
				suffix_max += sequence[i];
				glob_max = suffix_max;
				l = sl;
				r = i;
			}
			else if(sequence[i] + suffix_max >= 0){
				suffix_max += sequence[i];
			}
			else{
				suffix_max = 0;
				sl = (i+1);
			}
		}
		return new SubSequence(l, r, glob_max);
	}

Mit
Java: 
return new SubSequence(l, r, glob_max);
scheine ich richtig zu liegen, weil ich mit start und sum jetzt bei den richtigen Ergebnissen liege. length nimmt aber noch nicht den richtigen Wert an. Weiß jemand warum?
 
L

Lukases2

Aktives Mitglied
Fehlt irgendeine wichtige Information, so dass mir nicht geholfen werden kann? Mit "Teilfolge maximaler Summe" ist gemeint, dass ich eben jene Teilfolge ermitteln soll, deren Summe größer ist, als jede andere Summe einer Teilfolge.
Beispiel
F = {a[1], ... a[n]} := {1,4,-1,2}
Ergebnis wäre hier: F[1,2], weil 1+4 > jede andere Teilfolge.
Die Methode soll dann ausgeben: start: 1, length: 2, sum = 5
Das tut sie nur leider im Moment noch nicht. Kann mir einer weiterhelfen?

[Sollte dieser Beitrag unnötig sein, kann er gerne wieder gelöscht werden. Ich wollte hiermit nicht pushen.]
 
J

JuliaJulia

Neues Mitglied
Hallo,

sitze auch an dieser Aufgabe und habe genau das selbe Problem, denn das Programm an sich habe ich exakt genauso.
Mein Problem ist ebenfalls die Ausgabe. Was jedoch nicht stimmt ist "return new SubSequence(l, r, glob_max)", denn die Ausgabe des Anfangswert stimmt zwar bei den ersten drei Werten, aber nicht bei den Weiteren. Deshalb ist bisher nur glob_max richtig. Weiß aber leider auch nicht weiter ???:L???:L???:L
 
K

klausr

Mitglied
Zunächst muss l und r um eins verschoben werden, wegen der Arrayindizierung. SubSequence(l, r, glob_max) ist falsch. SubSequence(linker Index, Länge, glob_max) ist richtig, wobei Länge = r-l +1.

Berücksichtigt werden muss noch, dass der gegebene Algorithmus teils noch 0 am Anfang in der ermittelten Folge hat, wegen denen l verschoben werden kann.
 
Zuletzt bearbeitet:
T

TrissyGE

Neues Mitglied
Code: 
    static SubSequence optimalMaxSubSequence(int[] sequence) {
         

        int glob_max = 0;
        int suffix_max = 1;
        int l = -1, r = -2;
        int sl = 1;
 
        for(int i = 0; i < sequence.length; i++){
            if(sequence[i] + suffix_max > glob_max){

                suffix_max += sequence[i];
                glob_max = suffix_max;
                l = sl;
                r = i;
            }
            else if(sequence[i] + suffix_max >= 0){
                suffix_max += sequence[i];
            }
            else{
                suffix_max = 0;
                sl = (i+1);
            }
        }
        int Länge = r-l+1;
        return new SubSequence(l, Länge, glob_max);
    }

Hab den code mit der hilfe hier im Forum so aufgeschrieben und die Variablen angepasst, soweit so gut. Bei 10 ausgaben sagt mit das Programm bei 8 es sei richtig und bei 2en, es sei falsch, jemand ne ahnung warum?? Ist das bei euch auch so??

Edit: habs behoben
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen


Oben