Busca por submatriz com soma máxima (Algoritmo de Kadane)

Java Medium arrays

Tarefa «Busca por submatriz com soma máxima (Algoritmo de Kadane)»

Dada uma matriz de números inteiros. Encontre a submatriz (sequência contínua de elementos) com a soma máxima. Exiba essa soma. Se a matriz consistir apenas de números negativos, exiba o maior número negativo (ou seja, o menor em valor absoluto).

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 10^5) — a quantidade de elementos. A segunda linha contém N números inteiros, separados por espaços — os elementos da matriz.

Formato de Saída

Exiba um único número inteiro — a soma máxima da submatriz.

Exemplos

Exemplo 1

ENTRADA

3
abc
abcd
ab

SAÍDA

abcd

Exemplo 2

ENTRADA

4
-1 -2 -3 -4

SAÍDA

-1

Exemplo 3

ENTRADA

5
1 3 2 4 1

SAÍDA

11

Exemplo 4

ENTRADA

2
a
bb

SAÍDA

NO

main.java