Minimale absolute Summe eines Subarrays finden
Es gibt ein Array A , das (positive und negative) Ganzzahlen enthält. Suchen Sie nach einem (zusammenhängenden) Subarray, dessen absolute Summe der Elemente minimal ist, z. B .:
Ich habe mit der Implementierung eines Brute-Force-Algorithmus begonnen, der O(N^2) oder O(N^3) enthielt, obwohl er korrekte Ergebnisse lieferte. Aber die Aufgabe spezifiziert:
Nach einigem Suchen dachte ich, dass vielleicht Kadanes Algorithmus für dieses Problem modifiziert werden könnte, aber ich habe es nicht geschafft.
Meine Frage ist - ist Kadanes Algorithmus der richtige Weg? Wenn nicht, könnten Sie mir in die richtige Richtung zeigen (oder einen Algorithmus benennen, der mir hier helfen könnte)? Ich möchte keinen vorgefertigten Code, ich brauche nur Hilfe beim Finden des richtigen Algorithmus.
8 Antworten
Wenn Sie die Partialsummen berechnen
wie
Dann ist die Summe jedes zusammenhängenden Subarrays die Differenz zweier Partialsummen. Um also das zusammenhängende Subarray zu finden, dessen absoluter Wert minimal ist, schlage ich vor, dass Sie die Partialsummen sortieren und dann die beiden am nächsten liegenden Werte finden und die Positionen dieser beiden Teilsummen in der ursprünglichen Sequenz verwenden, um den Anfang und das Ende zu finden des Unterarrays mit dem kleinsten absoluten Wert.
Das teure Bit hier ist die Art, also ich denke, das läuft in Zeit O(n * log(n)) .
Ich machte diesen Test auf Codility und ich fand mcdowella Antwort recht hilfreich, aber nicht genug, ich muss sagen: Also hier ist eine 2015 Antwort Jungs!
Wir müssen die Präfixsummen von Array A (hier P genannt) wie folgt aufbauen: P [0] = 0, P [1] = P [0] + A [0], P [2] = P [1 ] + A [1], ..., P [N] = P [N-1] + A [N-1]
Die "min abs sum" von A wird die minimale absolute Differenz zwischen 2 Elementen in P sein. Also müssen wir einfach .sort() P durchlaufen und durchlaufen, wobei wir jedes Mal 2 aufeinanderfolgende Elemente nehmen. Auf diese Weise haben wir O (N + N log (N) + N), was gleich O (N log (N)) ist.
Das ist es!
Hier ist eine C-Lösung basierend auf Kadanes Algorithmus. Hoffentlich ist es hilfreich.
%Vor% Sie können Kadane's algorithm zweimal ausführen (oder es auf einmal tun), um die minimale und maximale Summe zu finden, in der das Suchminimum genauso funktioniert wie das Maximum mit umgekehrte Vorzeichen und berechnen Sie dann das neue Maximum, indem Sie ihren absoluten Wert vergleichen.
Quelle-Jemand (nicht erinnern, wer) Kommentar auf dieser Website.
Tags und Links algorithm sum dynamic-programming absolute-value kadanes-algorithm