Maximale Teilsumme ermitteln

[DaSt]

Hallo,

wir haben in der Vorlesung die Maximale Teilsumme besprochen und sollten sie nun implementieren.

Bsp.
Die M.T.S aus den Zahlen -13,25,34,12,-3,7,-87,28,-77,11 = 75 (25+34+12-3+7)

Nun hat der Prof. die "Musterlösung" online gestellt und ich verstehe nicht warum mein Code 11 als Ausgabe anstelle von 75 hat, da ich eig. exakt den gleichen code wie er habe.

Mein code:

public static void main(String[] args) {

     int arr[]={-13,25,34,12,-3,7,-87,28,-77,11};
    
     int erg=maxTeilSumme(arr,arr.length);
    
     System.out.println("Maximale Teilsumme: "+erg);
   }
  
   public static int maxTeilSumme(int arr[], int n){
    
     int maximum = -99999999;
     int erg;
    
     for(int i=0; i<n; i++){
       erg=0;
       for(int y=i; y<n; y++)
        
         erg+=arr[y];
         if(erg>maximum){
           maximum= erg;
         }
        
        
     }
    
     return maximum;
   }

Code aus der Musterlösung:

intMaxTeilsum2(int a[],int n) {
          
            inti, j, sum, max= int.MinValue;

            for(i=0; i<n; i++) {
                sum=0;
                  for(j=i; j<n; j++) {
                         sum+= a[j];
                          if(sum> max) max= sum;
                     }
            }
return max;
}

Könnt ihr mir sagen, warum mein Code nicht klappt?

Danke

 

[Xyz1]

Kannst du schnell erklären, was die maximale Teilsumme ist?
Und nimm doch: [code=Java][/code].

 

[DaSt]

Die Maximale Teilsumme ist die größte Quersumme die in einem Zahlenarray vorkommt.
Bei -5,6,5 ist die normale Quersumme ja 6 aber die M.T.S. = 11 (6+5) also die maximale Quersumme die aus den 3 Zahlen zu bilden ist.

Ich habe gerade bemerkt, dass mir in der 2ten for-Schleife die {} gefehlt haben und somit wurde das Erg. nicht richtig berechnet...

Hier der funktionierende Code

public static int maxTeilSumme(int arr[], int n) {

     int maximum = -999999999;
     int erg = 0;

     for (int i = 0; i < n; i++) {
       erg = 0;
       for (int y = i; y < n; y++) {

         erg = erg + arr[y];
         if (erg > maximum) {
           maximum = erg;

         }
       }

     }

     return maximum;
   }

 

[kneitzel]

Deine innere for-Schleife hat keine {}, daher umfasst diese nur den ersten Befehl und nicht den ganzen Block.

 

[Xyz1]

Hier der funktionierende Code

Ja ich Fauli hab nicht die öffnenden und schließenden Klammern gezählt...

Ich hab mich auch mal dran versucht, so sollte es sein:

    /**
     * @author DerWissende on 03/23/2016
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxPartSum(new int[]{-13, 25, 34, 12, -3, 7, -87, 28, -77, 11})));
        for (int i = maxPartSum(new int[]{-13, 25, 34, 12, -3, 7, -87, 28, -77, 11})[0]; i <= maxPartSum(new int[]{-13, 25, 34, 12, -3, 7, -87, 28, -77, 11})[1]; i++) {
            System.out.print(new int[]{-13, 25, 34, 12, -3, 7, -87, 28, -77, 11}[i] + " ");
        }
    }

[1, 5, 75]
25 34 12 -3 7

Das stimmt auch mit deiner ich nun verstehenten Erklärung überein.

 

[Xyz1]

Sry, gestern schon etwas "beschwipst" gewesen, so sein:

    /**
     * @author DerWissende on 03/24/2016
     * @param args
     */
    public static void main(String[] args) {
        int[] array = new int[]{-13, 25, 34, 12, -3, 7, -87, 28, -77, 11};
        System.out.println(Arrays.toString(array));
        int[] mps = maxPartSum(array);
        System.out.println(Arrays.toString(mps));
        for (int i = mps[0]; i <= mps[1]; i++) {
            System.out.print(array[i] + " ");
        }
    }

    private static int[] maxPartSum(int[] array) {
        // so zu implementieren wie bei dir / Prof.
    }

[-13, 25, 34, 12, -3, 7, -87, 28, -77, 11]
[1, 5, 75]
25 34 12 -3 7

Mir ist dann aufgefallen, dass der Algo n^2/2 bzw. n^2 benötigt, im Internet stand aber etwas von n+k bzw. n.

Also ist da noch Nachbesserungsbedarf. Es gibt unterschiedliche Ansaätze, das zu lösen.

Wie weit biste?

 

[Flown]

@DerWissende hat recht. Dieses Problem kann in O(n) gelöst werden. HIER sind auch noch ein paar andere Algorithmen (auch der Effizienteste).