Maximale Summe eines Subarrays mit Auslassungen

Kotlin Hard lists

Aufgabe «Maximale Summe eines Subarrays mit Auslassungen»

Gegeben ist eine Liste von ganzen Zahlen. Es ist die maximale Summe eines Subarrays (einer zusammenhängenden Folge von Elementen) zu finden, unter der Bedingung, dass aus diesem Subarray höchstens ein Element entfernt werden darf (um eine größere Summe zu erhalten). Das Entfernen eines Elements ist optional. Wenn die Liste leer ist, gilt die Summe als 0. Die Länge der Liste beträgt bis zu 10^5, die Elemente von -10^4 bis 10^4.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 100000) — die Anzahl der Elemente in der Liste. Die zweite Zeile enthält N ganze Zahlen, getrennt durch Leerzeichen.

Ausgabeformat

Eine ganze Zahl — die maximal mögliche Summe des Subarrays nach dem Entfernen von höchstens einem Element.

Beispiele

Beispiel 1

EINGABE

3
10 20 30

AUSGABE

60

Beispiel 2

EINGABE

1 2 3

AUSGABE

2

main.kt