Búsqueda del subarreglo con suma máxima (Algoritmo de Kadane)

Java Medium arrays

Tarea «Búsqueda del subarreglo con suma máxima (Algoritmo de Kadane)»

Dado un arreglo de números enteros. Encuentre el subarreglo (secuencia continua de elementos) con la suma máxima. Imprima esta suma. Si el arreglo consiste solo de números negativos, imprima el número negativo máximo (es decir, el de menor valor absoluto).

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 10^5) — la cantidad de elementos. La segunda línea contiene N números enteros, separados por espacios — los elementos del arreglo.

Formato de salida

Imprima un único número entero — la suma máxima del subarreglo.

Ejemplos

Ejemplo 1

ENTRADA

3
abc
abcd
ab

SALIDA

abcd

Ejemplo 2

ENTRADA

4
-1 -2 -3 -4

SALIDA

-1

Ejemplo 3

ENTRADA

5
1 3 2 4 1

SALIDA

11

Ejemplo 4

ENTRADA

2
a
bb

SALIDA

NO

main.java