Suche nach der maximalen Summe eines Subarrays nach einer zyklischen Verschiebung

Kotlin Hard loops

Aufgabe «Suche nach der maximalen Summe eines Subarrays nach einer zyklischen Verschiebung»

Gegeben ist ein Array von ganzen Zahlen. Es ist erlaubt, genau eine zyklische Verschiebung nach links (das erste Element wird zum letzten) oder nach rechts (das letzte Element wird zum ersten) beliebig oft, jedoch nicht öfter als die Array-Länge, durchzuführen. Danach muss die maximale Summe eines zusammenhängenden Subarrays (unter Verwendung des Kadane-Algorithmus) gefunden werden. Es soll die größtmögliche Summe ermittelt werden, die nach der Durchführung einer zyklischen Verschiebung erreicht werden kann. Ist das Array leer, wird 0 ausgegeben.

Eingabeformat

Erste Zeile: eine ganze Zahl N (1 ≤ N ≤ 10^6) — die Länge des Arrays. Zweite Zeile: N ganze Zahlen, durch Leerzeichen getrennt (jeweils betragsmäßig ≤ 10^9).

Ausgabeformat

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

Beispiele

Beispiel 1

EINGABE

4
-1 -2 -3 -4

AUSGABE

-1

main.kt