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

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

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

Как отвечать

Сначала уточните условие: подпоследовательность (элементы не обязаны идти подряд) или подмассив, строгое убывание или нестрогое. Для подмассива хватает одного прохода за O(n).

Дальше два подхода:

• динамика за O(n²): dp[i] хранит длину лучшей убывающей подпоследовательности, заканчивающейся на i, и перебирает все j < i с a[j] > a[i]. Память O(n). На n = 10⁵ это около 5·10⁹ сравнений, для CPython неподъёмно;
• бинарный поиск за O(n log n): массив tails, где tails[k] хранит наибольший возможный последний элемент убывающей подпоследовательности длины k + 1. Проще всего сменить знак и решать LIS:

from bisect import bisect_left

def lds_length(a):
    tails = []
    for x in a:
        i = bisect_left(tails, -x)
        if i == len(tails):
            tails.append(-x)
        else:
            tails[i] = -x
    return len(tails)

bisect_left даёт строгое убывание, bisect_right нестрогое. Чтобы восстановить ответ, храните индекс последнего элемента для каждой длины и ссылку на предыдущий, асимптотика не меняется.

Про ограничение снизу: в модели сравнений задача требует Ω(n log n) операций, это доказанный результат, так что второе решение асимптотически оптимально.

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

Выдают tails за ответ. Это служебный массив, его элементы могут вообще не образовывать подпоследовательность исходного массива.

Путают, что хранить в tails для убывания. Нужен наибольший хвост, а не наименьший: чем больше последний элемент, тем больше у последовательности шансов продолжиться.

Не различают строгое и нестрогое убывание и берут не ту функцию bisect. На массиве с повторами ответы разойдутся.