Teilfolge maximaler Summe

winfocgn

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

Code

[B]public[/B] [B]class[/B] Teilfolge { 
 
   [B]int[/B][] TeilfolgeMaxSumme([B]final[/B] [B]int[/B][] folge) { 
 
      [B]int[/B][][] s = [B]new[/B] [B]int[/B] [folge.length] [folge.length]; 
      [B]int[/B][] max = [B]new[/B] [B]int[/B][3]; 
      max[2] = Integer.MIN_VALUE; 

      [B]int[/B][] leer = [B]new[/B] [B]int[/B][3]; 
      leer[0] = 0; 
      leer[1] = 0; 
      leer[2] = 0; 
 
      [B]for[/B] ([B]int[/B] i = 0; i < folge.length; i++) { 
         [B]for[/B] ([B]int[/B] j = 0; j < folge.length; j++) { 
            s[i][j] = 0;    
         } 
      }    
 
      s[0][0] = folge[0];  
 
      [B]for[/B] ([B]int[/B] bis = 1; bis < folge.length; bis++) { 
         s[0][bis] = s [0][bis - 1] + folge[bis]; 
      } 
 
      [B]for[/B] ([B]int[/B] von = 1; von < folge.length; von++) { 
         [B]for[/B] ([B]int[/B] bis = von; bis < folge.length; bis++) { 
            s[von][bis] = s[von - 1][bis] - folge[von - 1]; 
         } 
      } 

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


      [B]if[/B] (folge.length == 0)  
         [B]return[/B] leer; 

      [B]else[/B]  
         [B]return[/B] max; 
   } 
 
   [B]public[/B] [B]static[/B] [B]void[/B] main(String[] args) { 
 
      Teilfolge t = [B]new[/B] Teilfolge(); 
      [B]final[/B] [B]int[/B][] folge = {-1, 3, 2, -4, 5, -7, 2, 2, -3, 5, -2, 3, -8, 2}; 
      [COLOR=#689868]//[B]final[/B] [B]int[/B][] folge = {0};[/COLOR] 
 
      [B]int[/B][] erg = [B]new[/B] [B]int[/B][2]; 
      erg = t.TeilfolgeMaxSumme(folge); 
 
      System.out.println(erg[0] + " " + erg[1] + " " + erg[2]); 
   } 
}

Alles anzeigen

lj_scampo

das problem liegt meiner meinung nicht in der ausgabe sondern in der "bestueckung": max[0] und max[1] wird niemals ein wert zugewiesen. deine funktion TeilfolgeMaxSumme liefert an stelle 0 und 1 also nur werte, falls du ein leeres array (folge.length==0) uebergibst

winfocgn

Hi lj_scampo,

danke für deine Antwort! Ja, das ist mir schon klar: im Moment werden die Variablen max[0] und max[1] als 0 in der Ausgabe ausgegeben: 0 0 7.

Ich bin quasi auf der Suche nach der Stelle, an der ich die beiden die Variablen max[0] und max[1] mit den gewünschten Werten bestücken kann. Also max[0]=<nummer der ersten teilfolgenelements> und max[0]=<nummer des letzten teilfolgenelements>

Vielen Dank für jede Hilfe!

Gruß,
winfo

winfocgn

Hi lj_scampo, hi zusammen,

Habe mittlerweile die Lösung gefunden. Habe einfach die Schleife

Code

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

Code

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!

Danke nochmal an alle!

Gruß,
winfo

winfocgn

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, winfo

Hier nochmal der vollständige, funkionierende Code:

Code

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 
   } 
}

Alles anzeigen

winfocgn

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

Viele Grüße,
winfo

Jetzt mitmachen!