Чат Telegram
Группа ВКонтакте

Максимальная сумма подряд идущих чисел

MEDIUM

На вход подается строка целых чисел, разделенных пробелами.

Нужно найти последовательность подряд идущих чисел, у которой сумма элементов будет максимальной.

Например, для строки "-2 1 -3 4 -1 2 1 -5 4" решением будет последовательность "4 -1 2 1" с максимальной суммой элементов равной "6".

Вывести нужно максимальную сумму подряд идущих элементов.

Нужно учитывать, что последовательность может представлять собой лишь одно число (смотрите пример с отрицательными числами).

Пример #1

Input

-8 -3 -6 -2 -5 -4

Output

-2

Пример #2

Input

-2 1 -3 4 -1 2 1 -5 4

Output

6

Решение