Ctrl K

Палиндром из сумм соседей

Средняя
Дан массив положительных целых чисел values. За одну операцию можно взять два соседних элемента и заменить их одним — их суммой. Например, из [3, 1, 2, 5] можно получить [3, 3, 5]. Верните наименьшее число операций, после которых массив станет палиндромом, то есть будет читаться одинаково слева направо и справа налево.
Пример 1
values=[3, 1, 2, 5, 3] → 2

Склеиваем 1 и 2 — получаем [3, 3, 5, 3]; затем 3 и 5 справа от первой тройки — [3, 8, 3]. Это палиндром, хватило двух операций.

Пример 2
values=[6, 2, 6] → 0

Массив уже палиндром — операции не нужны.

Пример 3
values=[1, 4, 2] → 2

Края 1 и 2 никак не уравнять, не слив всё в одно число: нужно две операции.

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

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