Поиск подмассива с максимальной суммой (Kadane's algorithm)

Java Средний arrays

Задача «Поиск подмассива с максимальной суммой (Kadane's algorithm)»

Дан массив целых чисел. Найдите подмассив (непрерывную последовательность элементов) с максимальной суммой. Выведите эту сумму. Если массив состоит только из отрицательных чисел, выведите максимальное отрицательное число (то есть наименьшее по модулю).

Формат ввода

Первая строка содержит целое число N (1 ≤ N ≤ 10^5) — количество элементов. Вторая строка содержит N целых чисел, разделённых пробелами — элементы массива.

Формат вывода

Выведите одно целое число — максимальную сумму подмассива.

Примеры

Пример 1

ВВОД

3
abc
abcd
ab

ВЫВОД

abcd

Пример 2

ВВОД

4
-1 -2 -3 -4

ВЫВОД

-1

Пример 3

ВВОД

5
1 3 2 4 1

ВЫВОД

11

Пример 4

ВВОД

2
a
bb

ВЫВОД

NO

main.java