Maximale Summe eines Subarrays mit zyklischer Verschiebung

PHP Hard arrays

Aufgabe «Maximale Summe eines Subarrays mit zyklischer Verschiebung»

Gegeben ist ein Array ganzer Zahlen. Es soll die maximale Summe eines Subarrays (einer zusammenhängenden Folge von Elementen) gefunden werden, nachdem genau eine zyklische Verschiebung nach links um eine beliebige Anzahl von Positionen (von 0 bis N-1) angewendet wurde. Falls das Subarray nach der Verschiebung leer sein kann, wird die Summe des leeren Subarrays als 0 betrachtet. Das Subarray muss mindestens ein Element enthalten, wenn alle Elemente negativ sind. Einschränkungen: Array-Länge von 1 bis 10^5, Elemente von -10^9 bis 10^9.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 100000) — die Größe des Arrays. Die zweite Zeile enthält N ganze Zahlen — die Elemente des Arrays.

Ausgabeformat

Eine ganze Zahl — die maximale Summe des Subarrays nach einer zyklischen Verschiebung nach links.

Beispiele

Beispiel 1

EINGABE

5

AUSGABE

10

Beispiel 2

EINGABE

-3

AUSGABE

-6

main.php