Schreiben Sie eine Methode, die das Maximum–Sub-Array–Problem im Divide-and-Conquer–Verfahren löst. Die Rückgabe der maximalen Summe genügt, Indizes dafür brauchen nicht ermittelt zu werden. Das zu bearbeitende Array des Typs int[] soll dieser Methode als Parameter übergeben werden.
Verwenden Sie beim „Join“ die Methoden findLeftEdgeMaximum und findRightEdgeMaximum der Klasse SubArray zum Ermitteln der Randmaxima. Rufen Sie diese Klassenmethoden auf wie im folgenden Beispiel:
int untergrenze, obergrenze; int linkesRandMaximum; … linkesRandMaximum = SubArray.findLeftEdgeMaximum(array, untergrenze, obergrenze).getSum();
Die Unter- und Obergrenze definieren denjenigen Teil des Arrays, von dem das Randmaximum gesucht werden soll; diese Grenzen gehen aus Ihrem Algorithmus hervor. Die Variable linkesRandMaximum hat nach Ausführung der obigen Anweisung dann genau den Wert der höchstmöglichen Summe aller Sub-Arrays, die in array bei untergrenze beginnen.
Verwenden Sie die Java-Anwendung „MsaRacer“ zur Analyse des Laufzeitverhaltens der vier implementierten Lösungsverfahren des Maximum–Sub-Array–Problems. Die Anwendung besteht aus einem Java-Archiv, in dem alle .class- und .java-Dateien gebündelt sind. Starten Sie die Anwendung durch Doppelklick auf die .jar-Datei oder durch folgenden Kommandozeilen-Befehl: $ java -jar MsaRacer.jar
Die Anwendung „MsaRacer“ finden Sie bei den Maximum–Sub-Array–Unterlagen.
Ergänzend können Sie im Mac-Pool das Unix-Werkzeug „time“ auf der Kommandozeile wie folgt benutzen: $ time java Klassenname
$Id: HEADER.html,v 1.3 2008/06/04 18:24:12 aj3 Exp $
Name Last modified Size Description
Parent Directory -
RandomisedArrayFactory.java 2023-10-11 10:00 5.7K
HEADER.html 2023-10-11 10:00 2.6K
Loesung82.png 2023-10-11 10:00 64K
