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.
Zunächst ist es unnötig, Sub-Arrays doppelt zu bestimmen, nämlich von i nach j und von j nach i. Aufgrund der Kommutativität der Addition sind diese Summen jeweils identisch für alle i und j. Folglich genügt es, die j-Schleife bei i zu beginnen. Dies halbiert den Rechenaufwand immerhin, was aber an dessen Größenordnung von O(n³) natürlich noch nichts ändert.
Eine weitergehende Verbesserung erreicht man, indem nicht mehr für jeden der jetzt ca. (n² / 2) Sub-Arrays jeweils eine eigene Schleife mit O(n) laufen lässt, um dessen Summe zu ermitteln. Statt dessen kann man in einer der beiden ohnehin vorhandenen Zählschleifen für die Indizes i und j die Summe direkt mitzählen. Die innerste Schleife (k-Schleife) wird dadurch überflüssig, und Rechenaufwand so auf eine Größenordnung auf O(n²) verbessert.
Parameter: Array A (Länge n)
Gesucht: Höhe der maximalen Teilsumme
Java-Quellcode: Loesung72.java
Arne Johannessen, 12. Juni 2009