maximales Sub-Array Problem von Bentley
-
Vielleicht kennt ja jemand das maximale Subarray Problem von Jon Bentley (aus dem Buch Programming Pearls). Ich habe hier drei Algorithmen zur Lösung des Problems. Einmal Brute Force, ein rekursives Verfahren und das 'Inspektionsverfahren'. Nun möchte ich den Start- und Endindex des maximalen Subarrays ausgeben. Bei Brute Force ist das ja kein Problem, aber bei den anderen beiden habe ich doch arge Probleme.
Bei dem Inspektionsverfahren bekomme ich bei sehr großen Arrays ungefähr jedes 10. mal einen falsche Anfangsindex. Irgendeine Bedingung habe ich also übersehen.
Hat irgend jemand schon mal dieses Problem gelöst und könnte mir weiterhelfen? (im Netz habe ich zu dieser Problemstellung auch nichts gefunden).