Es gibt ein ArrayA enthält (positive und negative) ganze Zahlen. Suchen Sie ein (zusammenhängendes) Subarray, dessen absolute Summe der Elemente minimal ist,

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

Ich habe mit der Implementierung eines Brute-Force-Algorithmus begonnen, derO(N^2) oderO(N^3), obwohl es zu korrekten Ergebnissen führte. Aber die Aufgabe gibt an:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

Nach einiger Suche dachte ich, dass vielleicht Kadanes Algorithmus geändert werden kann, um dieses Problem zu lösen, aber ich habe es nicht geschafft.

Meine Frage ist - ist Kadanes Algorithmus der richtige Weg? Wenn nicht, könnten Sie mich in die richtige Richtung lenken (oder einen Algorithmus nennen, der mir hier helfen könnte)? Ich möchte keinen vorgefertigten Code, sondern brauche nur Hilfe bei der Suche nach dem richtigen Algorithmus.