Interface MaximumSubArraySolver

public interface MaximumSubArraySolver

Schnittstelle fuer die Loesung des Maximum-Sub-Array--Problems.

Die folgende Klasse zeigt beispielhaft, wie der Rumpf einer Loesung aussehen koennte:

 public class MsaProblemLoeser implements MaximumSubArraySolver {
     
     public SubArray findMaximumSubArray (int[] array) {
         SubArray ergebnis;
         
          // Loesungs-Algorithmus hier
          // (siehe Manuskript)
         
         return ergebnis;
     }
     
     
     public static void main (String[] args) {
         
          // Vorbereitung des Eingabewerts
         int[] array = SubArray.createRandomArray();
         
          // Berechnung des Ergebnisses
         MsaProblemLoeser problemLoeser = new MsaProblemLoeser();
         SubArray maximumSubArray = problemLoeser.findMaximumSubArray(array);
         
          // Ausgabe des Ergebnisses
         System.out.println(maximumSubArray);
         System.out.println("Summe: ["+maximumSubArray.getSum()+"]");
     }
 }
 

Version:

$Revision: 1.1 $

Author:

Arne Johannessen

See Also:

SubArray

Method Summary

SubArray

findMaximumSubArray(int[] array) Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array.

Method Detail

findMaximumSubArray

SubArray findMaximumSubArray(int[] array)

Loest das Maximum-Sub-Array--Problem fuer den uebergebenen Array.

Die Loesung ist genau diejenige Teilfolge des Gesamt-Arrays, die von allen moeglichen Teilfolgen die hoechste Summe ihrer Elemente aufweist. Der Gesamt-Array kann sowohl positive als auch negative Zahlen beinhalten; die Implementierung muss dies beruecksichtigen. Existieren nur negative Elemente, ist die Teilfolge mit der hoechsten Summe die leere Teilfolge mit der Summe null (0).

Das Verhalten dieser Methode fuer array == null ist nicht definiert.

Parameters:

array - der fuer die Bestimmung der Problemloesung heranzuziehende Gesamt-Array

Returns:

eine neu erstellte Instanz der Klasse SubArray, deren Gesamt-Array identisch mit dem dieser Methode uebergebenen array ist und deren Sub-Array--Definition derart ist, dass sie eine korrekte Loesung des Maximum-Sub-Array--Problems darstellt.