Maximale Summe eines Subarrays mit Entfernung eines Elements

Java Hard arrays

Aufgabe «Maximale Summe eines Subarrays mit Entfernung eines Elements»

Gegeben ist ein Integer-Array. Es ist die maximale Summe eines Subarrays (einer zusammenhängenden Elementfolge) zu finden, unter der Bedingung, dass höchstens ein Element entfernt werden darf (oder keines entfernt wird). Das Subarray muss mindestens ein Element enthalten. Es ist ein Algorithmus mit einer Zeitkomplexität von O(n) und konstantem zusätzlichem Speicher zu implementieren.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl n (1 ≤ n ≤ 10^5) — die Anzahl der Elemente des Arrays. Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen — die Elemente des Arrays (der Betrag überschreitet 10^4 nicht).

Ausgabeformat

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

Beispiele

Beispiel 1

EINGABE

5 1
1 2 3 2 4

AUSGABE

9

Beispiel 2

EINGABE

2
7 1
-4 3

AUSGABE

8

Beispiel 3

EINGABE

6
2 -1 2 3 4 -5

AUSGABE

11

main.java