Ctrl K

Подпоследовательности с равным шагом

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

Подходят [1, 2, 3], [2, 3, 4] и [1, 2, 3, 4].

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

Шаг 0 подходит любой подпоследовательности: четыре тройки и одна четвёрка позиций.

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

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