Maximale kreisförmige Unterarraysumme

Question

Dies ist eine Frage von den Buchalgorithmen von Jeff Erickson.

Angenommen, a ist ein kreisförmiges Array. In dieser Einstellung kann ein "zusammenhängender Unterarray" entweder ein Intervall A [I. ... J] oder ein Suffix, gefolgt von einem Präfix A [I. ... N] · A [1 .. J]. Beschreiben und analysieren Sie einen Algorithmus, der eine zusammenhängende Unterarray von A mit der größten Summe findet. Das Eingabearray besteht aus realen Zahlen.

mein Ansatz:

Es gibt zwei Möglichkeiten

1) Keine Umwicklung (wir können Kadane-Algorithmus verwenden)

2.) Umwicklung (dh; Startindex des Unterarrays ist größer als der Endindex) (ich habe in diesem Fall Zweifel)

gibt jetzt das Maximum von zwei Fällen als Ergebnis zurück.

Für den zweiten Fall suchte das Suchen im Internet einen Ansatz ohne Beweis.

Der Ansatz besteht darin, den Unterarray mit minimaler Summe zu finden und ihn von der Summe des gesamten Arrays abzusetzen (dh; Summe (A) - min_subray_sum (A)). Wie ist diese Lösung korrekt?

Link für die im zweiten Fall verwendete Methode: https:// www. geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

let $ A $ Seien Sie Ihr Array, lassen Sie $ B $ einen kreisförmigen Unterarray von $ A $ das maximiert $ \ sum_ {b \ in B \ in B \ B $ , und lassen Sie $ C $ Seien Sie der Unterarray, der alle Elemente von $ A $ enthält, die nicht in sind> $ B $ . Beachten Sie, dass $ C $ auch ein kreisförmiger Unterarray ist.

Sie haben $ \ SUM_ {A \ in a} a=Sum_ {B \ in B \ in B \ B + \ SUM_ {C \ in c \ c} C $ , was bedeutet, dass $ \ sum_ {c \ in c} c=sum_ {a \ in a} a - \ sum_ {b \ in B} B $ . Da $ \ sum_ {a \ in A} A $ ein konstanter (WRT $ B $ ) und ist $ B $ Maximiert $ \ SUM_ {B \ in B} B $ , $ C $ Minimiert $ \ sum_ {c \ in c} c $ .

Darüber hinaus ist mindestens einer der $ B $ und $ C $ nicht nur kreisförmig, sondern auch Anhängesteulich und kann daher in $ o (n) $ Time gefunden werden.