Suche nach der maximalen Summe eines Subarrays unter Berücksichtigung negativer Elemente und zyklischer Verschiebung

TypeScript Hard loops

Aufgabe «Suche nach der maximalen Summe eines Subarrays unter Berücksichtigung negativer Elemente und zyklischer Verschiebung»

Gegeben ist ein Array von ganzen Zahlen. Es ist die maximale Summe eines Subarrays (einer zusammenhängenden Folge von Elementen) nach höchstens einer zyklischen Verschiebung des Arrays nach links oder rechts zu finden. Eine zyklische Verschiebung bedeutet, dass sich die Elemente wie im Kreis bewegen. Wird keine Verschiebung durchgeführt, wird das Subarray aus dem ursprünglichen Array ausgewählt. Wird eine Verschiebung durchgeführt, kann das Subarray aus dem Array nach der Verschiebung ausgewählt werden. Geben Sie die maximal mögliche Summe aus. Die Länge des Arrays beträgt 1 bis 10^5, die Elemente von -10^4 bis 10^4. Verwenden Sie den Kadane-Algorithmus unter Berücksichtigung der zyklischen Verschiebung.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N — die Anzahl der Elemente des Arrays. Die zweite Zeile enthält N ganze Zahlen, getrennt durch Leerzeichen.

Ausgabeformat

Eine ganze Zahl — die maximale Summe des Subarrays.

Beispiele

Beispiel 1

EINGABE

3
10 -5 10

AUSGABE

20

Beispiel 2

EINGABE

7
abacaba
2
3

AUSGABE

2
aba
acb

main.ts