Abgabe bis Montag, 15. Juni, 15:50 Uhr.
Das naïve Lösungsverfahren zum Maximum–Sub-Array–Problem mit kubischem Laufzeitverhalten ( O(n³) ) hat eine sehr unbefriedigende Performance. Überlegen Sie, auf welche Weise sich dieses Verfahren geringfügig verändern lässt, um wenigstens quadratisches Laufzeitverhalten ( O(n²) ) zu erreichen. Formulieren Sie den sich ergebenden Algorithmus in „natürlicher Sprache“ nach Dr. Bürg.
Schreiben Sie eine Klassenmethode, die den Algorithmus aus Aufgabe 7-1 implementiert; sie soll auf einem Array des Typs int[] arbeiten, der als Parameter übergeben wird. Als Ergebnis genügt bei dieser Aufgabe die Rückgabe der Sub-Array–Summe.
Die Rückgabe der Sub-Array–Summe reicht nicht aus, um den Sub-Array identifizieren zu können. Ein Sub-Array wird stattdessen üblicherweise definiert über eine Referenz zu dem Gesamt-Array, von dem er ein Teil ist, sowie den Start-Index und die Länge des Sub-Arrays als dessen Grenzen. Alternativ ist die Bezeichnung der Grenzen auch mit Beginn-Index und End-Index möglich.
Implementieren Sie eine Klassenmethode analog zu Aufgabe 7-2, die anstatt der Summe des Sub-Arrays dessen Definition als Objekt vom Typ TeilArray zurückgibt! Benutzen Sie dazu die Klasse TeilArray aus Aufgabe 6-2.
Tipp. Ermitteln Sie zunächst die Grenzen des Sub-Arrays. Überprüfen Sie diese mit Hilfe von System.out.println(int) oder eines Debuggers, bevor Sie die Rückgabe des TeilArray-Objekts implementieren. Für die Rückgabe müssen Sie zunächst ein neues Objekt erzeugen, z. B. so:
TeilArray subarray = new TeilArray();
$Id: HEADER.html 2009-06-09 $
Name Last modified Size Description
Parent Directory -
HEADER.html 2023-10-11 10:00 2.2K
Loesung72.java 2023-10-11 10:00 1.6K