Für das Maximum–Sub-Array–Problem existieren verschiedene Lösungsansätze. Diese Web-Anwendung führt die Arbeitsweise einer Lösung nach dem Divide-and-Conquer–Prinzip vor. Gesucht ist ledglich der Zahlenwert des größten Arrayteils.
Das Lösungsverfahren teilt den Array in zwei Hälften auf (divide), löst das Maximum–Sub-Array–Problem für beide Hälften getrennt (conquer) und setzt hinterher aus den Teilergebnissen die Lösung zusammen (join). Beim Lösen der beiden Hälften wird das gleiche Verfahren rekursiv angewandt.
Nach jeder Trennung kann sich der gesuchte Sub-Array ganz in der linken Hälfte oder ganz in der rechten Hälfte befinden. Es ist aber auch möglich, dass er sich über die Trennstelle hinweg erstreckt. Dieser Möglichkeit muss durch Berechnung und Addition der Randmaxima an der Trennstelle in beide Richtung Rechnung getragen werden; diese wird in der Vorführung in der Horizontalen gezeigt.
28. Januar 2010, Version 1.0.2
Antonia Boemanns, Bianca Förster, Arne Johannessen, Holger SchroppSkriptsprachen / Objektorientierte Programmierung
Fakultät für Geomatik, Studienrichtung Kartographie
Hochschule Karlsruhe – Technik und Wirtschaft