Ctrl K

Растущая цепочка мелкими шагами

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

Цепочка 3, 4, 5 растёт шагами по 1 — длина 3. А, например, 1, 2, 5 не годится: 5 − 2 = 3 > 2. Длиннее трёх собрать не выйдет.

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

Значения должны строго расти, поэтому из одинаковых чисел берём только одно.

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

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