Recherche du sous-tableau à somme maximale (Algorithme de Kadane)

Java Medium arrays

Tâche «Recherche du sous-tableau à somme maximale (Algorithme de Kadane)»

Étant donné un tableau d'entiers. Trouvez le sous-tableau (séquence continue d'éléments) ayant la somme maximale. Affichez cette somme. Si le tableau ne contient que des nombres négatifs, affichez le plus grand nombre négatif (c'est-à-dire le plus petit en valeur absolue).

Format d\ entrée

La première ligne contient un entier N (1 ≤ N ≤ 10^5) — le nombre d'éléments. La deuxième ligne contient N entiers, séparés par des espaces — les éléments du tableau.

Format de sortie

Affichez un seul entier — la somme maximale du sous-tableau.

Exemples

Exemple 1

ENTRÉE

3
abc
abcd
ab

SORTIE

abcd

Exemple 2

ENTRÉE

4
-1 -2 -3 -4

SORTIE

-1

Exemple 3

ENTRÉE

5
1 3 2 4 1

SORTIE

11

Exemple 4

ENTRÉE

2
a
bb

SORTIE

NO

main.java