Лучший отрезок оценок с одним «пропуском»

Перед контрольной учитель вывесил в дневнике подряд результаты мини-тестов класса: за каждый урок — одно число (может быть отрицательным, если за урок получился «минус к настроению»).

Ты выбираешь подряд идущий отрезок уроков, чтобы показать, что прогресс был максимальным. Но разрешают один раз «не учитывать» ровно один урок внутри выбранного отрезка (как будто его не было). Можно и не пропускать ничего.

После пропуска (или без него) должно остаться хотя бы одно число.

Найди максимальную возможную сумму.

Важно: сумма может не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема.

Формат ввода

Первая строка: целое число n — количество уроков. Вторая строка: n целых чисел a1, a2, ..., an.

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

Одно целое число — максимальная сумма по некоторому непустому подряд идущему отрезку после удаления не более одного элемента внутри этого отрезка.

Ограничения

• 1 ≤ n ≤ 5000
• -100000 ≤ ai ≤ 100000

Пример

Ввод:

5
1 -2 0 3 -1

Вывод:

4

Ключевое наблюдение: «лучший отрезок» удобно строить слева направо. Если фиксировать, что отрезок обязан заканчиваться в текущей позиции i, то для следующего шага достаточно знать всего два числа — максимальную сумму в этом режиме.

Здесь работает 1D DP (динамика по массиву), потому что решение для позиции i зависит только от i-1: либо продолжаем отрезок, либо начинаем новый, а «пропуск» можно сделать один раз.

Заведём состояния:

• dp0 — максимум суммы непустого отрезка, заканчивающегося в i, без удалений.
• dp1 — максимум суммы непустого отрезка, заканчивающегося в i, с ровно одним удалением внутри этого отрезка.

Переходы для элемента x = a[i]:

• new_dp0 = max(x, dp0 + x) (либо стартуем с i, либо продолжаем).
• new_dp1 = max(dp1 + x, dp0):
• dp1 + x: удаление уже было раньше, сейчас просто добавили x;
• dp0: удаляем текущий x, тогда сумма равна лучшему «без удалений» на i-1.

План решения:

• Инициализируй dp0 = a[0], dp1 = -inf (на первом элементе нельзя «удалить и получить пусто»).
• Иди по i = 1..n-1, пересчитывай new_dp0, new_dp1.
• Ответ — максимум среди всех dp0 и dp1 на каждом шаге.

Сложность: O(n) по времени и O(1) по памяти.

Частая грабля: разрешить пустой отрезок после удаления. Поэтому dp1 нельзя начинать с 0; нужно -inf, и ответ всегда берётся из непустых состояний.