Schreiben Sie eine Klasse mit einer Klassenmethode, die das Maximum–Sub-Array–Problem im Divide-and-Conquer–Verfahren löst. Die Ausgabe der maximalen Summe genügt, Indizes dafür brauchen nicht ermittelt zu werden. Das zu bearbeitende Array 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.
Ändern Sie Ihre Lösung aus Aufgabe 4-1 derart, dass sie das Interface MaximumSubArraySolver implementiert.
(Anmerkung: Selbstverständlich soll der Algorithmus nicht geändert werden – es ist weiterhin das Divide-and-Conquer–Verfahren gefragt!)
$Id: HEADER.html,v 1.6 2007/12/04 22:44:28 arne Exp $
Name Last modified Size Description
Parent Directory -
doc/ 2023-10-11 10:00 - Klassendokumentation (Javadoc)
HEADER.html 2023-10-11 10:00 2.1K
Loesung41.java 2023-10-11 10:00 3.6K
MaximumSubArraySolver.java 2023-10-11 10:00 2.4K