Suche nach dem Teilarray mit der maximalen Summe (Kadane-Algorithmus)

Java Medium arrays

Aufgabe «Suche nach dem Teilarray mit der maximalen Summe (Kadane-Algorithmus)»

Gegeben ist ein Array aus ganzen Zahlen. Finden Sie das Teilarray (eine zusammenhängende Folge von Elementen) mit der maximalen Summe. Geben Sie diese Summe aus. Wenn das Array nur aus negativen Zahlen besteht, geben Sie die maximale negative Zahl (also die mit dem kleinsten Betrag) aus.

Eingabeformat

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

Ausgabeformat

Geben Sie eine ganze Zahl aus — die maximale Summe des Teilarrays.

Beispiele

Beispiel 1

EINGABE

3
abc
abcd
ab

AUSGABE

abcd

Beispiel 2

EINGABE

4
-1 -2 -3 -4

AUSGABE

-1

Beispiel 3

EINGABE

5
1 3 2 4 1

AUSGABE

11

Beispiel 4

EINGABE

2
a
bb

AUSGABE

NO

main.java