Abgabe bis Montag, 22. Juni, 15:50 Uhr.
Durch invariante Festlegung einer der beiden Sub-Array–Grenzen auf einen bestimmten Index lässt sich das derart eingeschränkte Maximum–Sub-Array–Problem leicht mit einer linearen Zeitkomplexität von O(n) lösen. Formulieren Sie einen Algorithmus, der das sog. linke Randmaximum ermittelt, dessen linke Grenze auf den Index 0
festgelegt ist.
Schreiben Sie wahlweise präzise „natürliche Sprache“ nach Dr. Bürg oder eine Java-Klassenmethode! In Java wird lediglich der Gesamt-Array als Parameter übergeben; es genügt die Rückgabe der Sub-Array–Summe als Ergebnis.
Formulieren Sie analog zu Aufgabe 8-1 einen Algorithmus, der das rechte Randmaximum ermittelt.
Der auf dem sog. Scanline-Prinzip arbeitende Algorithmus von Kadane bestimmt den Maximum–Sub-Array frei, indem an jeder Position des Arrays dasjenige Maximum–Sub-Array ermittelt wird, das an dieser Position seinen rechten Rand hat. Weil dieses Sub-Array immer entweder leer ist oder gerade um das eine Element an dieser Position länger ist als das an der vorhergehenden Position endende Maximum–Sub-Array, lässt sich mit diesem Algorithmus das Maximum–Sub-Array auch ohne eine invariante Grenze in linearer Zeitkomplexität lösen.
Implementieren Sie diesen Scanline-Algorithmus in Java in einer Klassenmethode! Es genügt die Rückgabe der Sub-Array–Summe als Ergebnis.
Überlegen Sie, welche Angaben ein in Aufgabe 8-1 ermitteltes Randmaximum eindeutig identifizieren würden.
$Id: HEADER.html 2009-06-14 $
Name Last modified Size Description
Parent Directory - HEADER.html 2023-10-11 10:00 2.4K Loesung81.java 2023-10-11 10:00 1.2K Loesung82.java 2023-10-11 10:00 1.3K Loesung83.java 2023-10-11 10:00 1.8K README.html 2023-10-11 10:00 957