Schreiben Sie eine weitere Methode zur Lösung des Maximum–Sub-Array–Problems. Ihre Lösung soll die Effizienz O(n) haben.
Erweitern Sie die Klasse, die Ihre Lösung zu Aufgabe 7-2 enthält, zu einem ausführbaren Programm. Schreiben Sie dazu eine Methode mit der Signatur public static void main (String[]) zum Testen der Klasse.
Bemerkenswert ist, dass die in der Vorlesung Algorithmen und Datenstrukturen 1 gezeigten Algorithmen zur Lösung des Maximum–Sub-Array–Problems allesamt lediglich die Summe des Ergebnisses berechnen. Das eigentlich benötigte Ergebnis ist aber natürlich der Sub-Array selbst.
Ein Array ist definiert durch seine Elemente, ein Sub-Array durch seine Grenzen und den gesamten Array. Die Grenzen können wahlweise entweder durch Beginn und Ende oder durch Start und Länge angegeben werden. Der durch die Klasse SubArray definierte Datentyp SubArray ist zur eindeutigen Definition eines Sub-Arrays geeignet.
Ändern Sie Ihre Lösung von Aufgabe 6-1 (naïves Verfahren) so ab, dass zusätzlich zur Summe die Grenzen des Sub-Arrays von der Methode zurückgegeben werden. Dazu muss statt der primitiven Datenstruktur int eine als Klasse definierte statische Datenstruktur der Rückgabetyp sein. Der Typ SubArray ist geeignet, andere Typen sind möglich.
$Id: HEADER.html,v 1.1 2008/06/04 14:29:32 aj3 Exp $
Name Last modified Size Description
Parent Directory -
SubArray.java 2023-10-11 10:00 28K
README.html 2023-10-11 10:00 961