Ich habe die folgende Implementierung von Kadanes Algorithmus in Java. Es ist im Grunde, die maximale Summe von zusammenhängenden Subarrays zu finden.
%Vor%Dies funktioniert jedoch nicht, wenn eine Kombination aus einer negativen und einer positiven Zahl in einem Array vorhanden ist, zum Beispiel das Folgende:
%Vor%Was sollte eine 12 als Maximum zurückgeben. Ab sofort gibt es 5
zurückZur obigen Antwort von Michał Šrajer:
Zeile # 7: max_ending_here = Math.max (0, max_ending_hier + x);
sollte sein:
max_ending_here = Math.max (x, max_ending_hier + x);
... nach dem Kadane-Algorithmus hier
Tags und Links algorithm java dynamic-programming kadanes-algorithm