Ctrl K

Отрезок с плюсами и минусами

Средняя
Дан массив целых чисел values. Возьмите непустой непрерывный отрезок values[i..j] и расставьте знаки по очереди, начиная с плюса: values[i] - values[i+1] + values[i+2] - .... Верните наибольшее значение такого выражения среди всех отрезков.
Пример 1
values=[4, 6, -3, 2] → 11

Отрезок [6, -3, 2]: 6 - (-3) + 2 = 11.

Пример 2
values=[-5, -1] → -1

Отрезок должен быть непустым. Лучший — [-1] со значением -1; у [-5, -1] получается -5 - (-1) = -4.

Пример 3
values=[1, 1, 1] → 1
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • -10⁵ ≤ values[i] ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиМеньше всего прыжков до конца СредняяСамая прибыльная серия дней СредняяДобраться до последней клетки СредняяМаршруты тележки по складу СредняяДешёвый маршрут из угла в угол Средняя
загружаем Python…
Вход
values=[4, 6, -3, 2]
Ожидается
11

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 133 теста на сервере, включая скрытые.