Как найти самую продолжительную убывающую последовательность в массиве чисел?

Что проверяют

Узнаёте ли вы в задаче классическую LIS с обратным знаком и умеете ли пройти путь от O(n²) к O(n log n). Следом просят восстановить саму последовательность, а не только длину, и спрашивают про повторяющиеся элементы.

Как отвечать

Сначала уточните условие: нужна подпоследовательность (элементы не обязательно подряд) или непрерывный отрезок. Отрезок решается одним проходом за O(n): считаете длину текущей серии и сбрасываете её, когда число не меньше предыдущего. Ещё уточните, строгое ли убывание.

Базовое решение для подпоследовательности: dp[i] это длина самой длинной убывающей подпоследовательности, заканчивающейся на arr[i]. Для каждого i перебираете j < i и при arr[j] > arr[i] обновляете dp[i] = max(dp[i], dp[j] + 1). Время O(n²), память O(n). Для восстановления храните prev[i] и идите по нему назад от индекса максимума.

Оптимальное решение за O(n log n) строится на массиве «хвостов» и модуле bisect. Числа инвертируют, и задача сводится к возрастающей подпоследовательности:

• tails[k]: минимальный хвост возрастающей подпоследовательности длины k + 1 среди инвертированных значений;
• шаг: для x = -a находите i = bisect_left(tails, x); при i == len(tails) добавляете, иначе заменяете tails[i] = x;
• нестрогое убывание: вместо bisect_left берут bisect_right, тогда равные элементы продлевают последовательность;
• восстановление: храните индекс элемента на каждой позиции tails и ссылку на предыдущий, иначе получите только длину.

Проговорите тесты: пустой массив, один элемент, возрастающий массив (ответ длины 1), все элементы равны, несколько ответов одной длины.

Где спотыкаются

Выдают tails за ответ. Это служебная структура: её значения могут принадлежать разным кандидатам и в исходном массиве идти не в том порядке.

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

Путают подпоследовательность с подмассивом и пишут O(n²) там, где хватает одного прохода, или наоборот.