ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2141. Саша Вилкин

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Саша Вилкин хочет кушать, так как уровень его сытости опустился до 0. По такому случаю он приходит в один из своих любимых ресторанов быстрого питания — «Лилка Вожка». Это заведение не зря стало его любимым, потому что как только он заходит внутрь, он попадает в новый мир, где еда работает совсем иначе...
Все блюда в этом чудесном месте обладают сытностью — неким целым числом. Если Саша съест какое-нибудь одно блюдо сытностью a, то его уровень сытости увеличится на a. В этом волшебном мире еда может и уменьшать уровень сытости (если сытность блюда отрицательна). К сожалению, желудок Саши не справляется, когда Саша ест много блюд подряд. Если он съедает несколько блюд с некоторыми сытностями, то каждое нечётное блюдо переваривается нормально, увеличивая сытость Саши на величину сытности этого блюда; но каждое чётное блюдо переваривается плохо, уменьшая сытость Саши на величину сытности этого блюда.
Изначально в ресторане находятся n блюд, которые лежат на стойке слева направо. Блюда пронумерованы числами от 1 до n в том порядке, в котором они лежат на стойке. Блюдо с номером i имеет сытность ai. Саша слишком торопится, чтобы обдумывать свой выбор, поэтому он хочет просто купить несколько подряд идущих блюд (или не купить ни одного). Сделав выбор, Саша съест все купленные блюда слева направо в том порядке, в котором они лежат, и ничего больше есть не будет. Помогите Саше найти максимально возможный уровень его сытости после того, как он съест свой обед.
Более формально: есть последовательность целых чисел ai. Нужно найти непрерывный отрезок последовательности (возможно, пустой), знакопеременная сумма которого максимальная. При этом первый элемент знакопеременной суммы всегда берётся со знаком плюс, независимо от его индекса.

Исходные данные

В первой строке дается целое число n — количество блюд в ресторане (1 ≤ n ≤ 105).
Во второй строке содержатся n целых чисел ai, записанных через пробел — сытности блюд (−105ai ≤ 105).

Результат

Выведите единственное целое число — максимальный уровень сытости Саши после того, как он пообедает. Учтите, что Саша может ничего не съесть, чтобы остаться максимально сытым.

Примеры

исходные данныерезультат
5
1 2 3 4 5
5
5
1 -2 3 -4 5
15
5
-1 -2 -3 -4 -5
2

Замечания

В первом примере Саше выгоднее всего просто съесть пятое блюдо, тогда уровень его сытости будет равен 5.
Во втором примере Саша может взять все блюда с первого по пятое, тогда знакопеременная сумма всех сытностей его блюд будет равна 15.
В третьем примере Саша может взять блюда с первого по четвёртое или со второе по пятое, тогда знакопеременная сумма всех сытностей блюд будет равна 2.
Автор задачи: Александр Ложкин
Источник задачи: Уральская командная олимпиада по программированию 2019