Suche nach der maximalen Summe eines Subarrays mit Vertauschungen

C# Medium arrays

Aufgabe «Suche nach der maximalen Summe eines Subarrays mit Vertauschungen»

Gegeben ist ein Array ganzer Zahlen. Es ist erlaubt, höchstens eine Operation durchzuführen: zwei Elemente des Arrays auszuwählen und ihre Positionen zu tauschen. Finden Sie die maximal mögliche Summe eines zusammenhängenden Subarrays (beliebiger Länge, einschließlich 0) nach höchstens einer Vertauschung. Wenn die Summe negativ sein kann, geben Sie 0 aus. Die Länge des Arrays beträgt 1 bis 10^5, die Elemente von -10^4 bis 10^4.

Eingabeformat

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

Ausgabeformat

Eine ganze Zahl — die maximale Summe des Subarrays.

Beispiele

Beispiel 1

EINGABE

3
-1 -2 -3

AUSGABE

0

Beispiel 2

EINGABE

5
1 2 3 4 5

AUSGABE

15

Beispiel 3

EINGABE

4
-1 2 3 -4

AUSGABE

5

main.cs