Teilfolge maximaler Summe

[babuschka]

Hallo zusammen,

komme bei folgendem Java-Code nicht so recht weiter. Es geht um das Problem "Teilfolge maximaler Summe", bei dem ich ein Tripel (von, bis, summe) ausgeben möchte. Die Berechnung der Summe funktioniert auch super (habe einen Algorithmus aus der Vorlesung in Java überführt). Und jetzt möchte ich halt nicht nur die Summe der Teilfolge ausgeben, sondern eben auch die Nummer des linken und rechten Elementes eben dieser Teilfolge. Stehe etwas auf dem Schlauch, habe schon alles mögliche ausprobiert - wäre super, wenn jemand einen Tipp für mich hätte.

Vielen Dank im voraus!
Gruß, squirrel

public class Teilfolge {

	int[] TeilfolgeMaxSumme(final int[] folge) {

		int[][] s = new int [folge.length] [folge.length];
		int[] max = new int[3];
		max[2] = Integer.MIN_VALUE;
		
		int[] leer = new int[3];
		leer[0] = 0;
		leer[1] = 0;
		leer[2] = 0;

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

		s[0][0] = folge[0]; 

		for (int bis = 1; bis < folge.length; bis++) {
			s[0][bis] = s [0][bis - 1] + folge[bis];
		}

		for (int von = 1; von < folge.length; von++) {
			for (int bis = von; bis < folge.length; bis++) {
				s[von][bis] = s[von - 1][bis] - folge[von - 1];
			}
		}
				
		for (int von = 0; von < folge.length; von++) {
			for (int bis = 0; bis < folge.length; bis++) {
				max[2] = Math.max(max[2], s[von][bis]);
			}
		}
		
		
		if (folge.length == 0) 
			return leer;
		
		else 
			return max;
	}

	public static void main(String[] args) {

		Teilfolge t = new Teilfolge();
		final int[] folge = {-1, 3, 2, -4, 5, -7, 2, 2, -3, 5, -2, 3, -8, 2};
		//final int[] folge = {0};

		int[] erg = new int[2];
		erg = t.TeilfolgeMaxSumme(folge);

		System.out.println(erg[0] + " " + erg[1] + " " + erg[2]);
	}
}

:bahnhof:

 

[Guest]

Hallo zusammen,

habe das Problem mittlerweile gelöst. Habe einfach

for (int von = 0; von < folge.length; von++) { 
  for (int bis = 0; bis < folge.length; bis++) { 
    max[2] = Math.max(max[2], s[von][bis]); 
  } 
}

mit

int firstElem = 0, lastElem = 0; 
for (int von = 0; von < folge.length; von++) { 
  for (int bis = 0; bis < folge.length; bis++) { 
    if (max[2] < s[von][bis]) { 
      firstElem = von; lastElem = bis; 
      max[2] = s[von][bis]; 
    } 
  } 
}

ersetzt. Funzt super!

Gruß,
squirrel

 

[Guest]

Hallo zusammen,

habe jetzt noch zwei (theoretische) Fragen zu meinem jetzt astrein funktionierenden Java-Prog, reaktiviere hiermit den Thread nochmal:

a) wie kann ich zeigen/begründen, dass mein Algorithmus terminiert?
b) Wie kann ich zeigen/begründen, dass der Algorithmus die Spezifikation erfüllt, dass wenn mehrere Teilfolgen maximaler Länge existieren, diejenige mit minimalem Beginn "von" und als 2. Kriterium mit minimaler Länge "bis-von" gewählt wird? -> Korrektheit

Vielen Dank im voraus und Grüße, squirrel

public class Maxsumme { 
   
   int[] TeilfolgeMaxSumme(final int[] folge) { 
   
      int[][] s = new int [folge.length] [folge.length]; 
      int[] max = new int[3]; 
      max[2] = Integer.MIN_VALUE; 
         
      int[] leer = new int[3]; 
      leer[0] = 0; 
      leer[1] = 0; 
      leer[2] = 0; 
   
      for (int i = 0; i < folge.length; i++) { 
         for (int j = 0; j < folge.length; j++) { 
            s[i][j] = 0;   
         } 
      }   
   
      s[0][0] = folge[0]; 
   
      for (int bis = 1; bis < folge.length; bis++) { 
         s[0][bis] = s [0][bis - 1] + folge[bis]; 
      } 
   
      for (int von = 1; von < folge.length; von++) { 
         for (int bis = von; bis < folge.length; bis++) { 
            s[von][bis] = s[von - 1][bis] - folge[von - 1]; 
         } 
      } 
               
      for (int von = 0; von < folge.length; von++) { 
        for (int bis = 0; bis < folge.length; bis++) { 
          if (max[2] < s[von][bis]) { 
         max[0] = von; max[1] = bis; 
            max[2] = s[von][bis]; 
          } 
        } 
      } 
     
      if (folge.length == 0) 
         return leer; 
         
      else 
         return max; 
   } 
   
   public static void main(String[] args) { 
   
  Maxsumme t = new Maxsumme(); 
      final int[] folge = {-1, 3, 2, -4, 5, -7, 2, 2, -3, 5, -2, 3, -8, 2}; 
      //final int[] folge = {0}; 
   
      int[] erg = new int[2]; 
      erg = t.TeilfolgeMaxSumme(folge); 
   
      System.out.println((erg[0]+1) + " " + (erg[1]+1) + " " + erg[2]); //+1, weil wir das Array bei 1 anfangen zu zählen 
   } 
}

 

[babuschka]

Hat sich erledigt!! Falls jemanden die Lösung interessiert, kann er mir gerne mailen.

Viele Grüße,
squirrel