Ctrl K

Восходящая цепочка через точку

Сложная
На плоскости дано n различных точек: points[i] = [x, y]. *Восходящая цепочка* — это последовательность точек из набора, в которой у каждой следующей точки **обе** координаты строго больше, чем у предыдущей. Верните наибольшую длину восходящей цепочки, в которую входит точка points[anchor].
Пример 1
points=[[4, 2], [1, 1], [6, 5], [3, 3], [5, 1]], anchor=3 → 3

Цепочка (1, 1) → (3, 3) → (6, 5) проходит через точку с индексом 3 и содержит три точки. Точку (4, 2) в неё не вставить: её y меньше, чем у (3, 3).

Пример 2
points=[[2, 8], [5, 4], [9, 0]], anchor=1 → 1

Точки идут вниз-вправо, ни одну пару нельзя поставить в цепочку, так что ответ — 1.

Пример 3
points=[[0, 0], [2, 0], [2, 2], [4, 4]], anchor=0 → 3
Ограничения
  • 1 ≤ n = len(points) ≤ 10⁵
  • points[i] = [x, y], 0 ≤ x, y ≤ 10⁹
  • Все точки различны
  • 0 ≤ anchor < n
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКоробка в коробке СложнаяK-я по величине разница в паре СложнаяСтрогий подъём из запасных чисел СложнаяСамый выгодный набор подработок СложнаяСамые выгодные выступления Сложная
загружаем Python…
Вход
points=[[4, 2], [1, 1], [6, 5], [3, 3], [5, 1]], anchor=3
Ожидается
3

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