Наибольшая невозрастающая подпоследовательность. Как оптимизировать алгоритм на Python?
Для начала рекомендую переотправить решение, таймауты могут случаться просто из-за всплеска нагрузки на тестирующий сервер.
Если это не поможет, то вам действительно стоит оптимизировать print, потому что в Python очень дорогие вызовы функций, на моём компьютере вот такие замеры получились:l = list(range(10**5))

for i in l:  # 107 ms
    print(i, end=' ')

s = ' '.join(map(str, l))
print(s)  # 55 ms
В целом при отладке таких проблем имеет смысл искать крайние случаи, на которых ваша программа будет работать медленнее всего — в данном случае, если я правильно понял вашу программу (читал не очень внимательно), это упорядоченный в обратном порядке массив размером 10^5.
UPD: Я нашёл плохой вход для вашей программы - проверьте её на массиве, где все значения одинаковые, время выполнения получилось около 20 секунд на массиве длиной 10^4, на 10^5 ответа я не дождался.
Это происходит вот из-за этих строк:for i in range(n):
    left = 1 
    right = l 
...
    elif x[m[mid]] == x[i]:
        left += 1
...
В худшем случае у вас здесь возникает O(n^2).
Кажется, достаточно будет просто поменять цикл на вот такой:for i in range(n):
    left = 1
    right = l

    while left <= right:
        mid = (left+right) // 2
        if x[m[mid]] <= x[i]:
            left = mid+1
        else:
            right = mid-1
...
Мадам, если этот реально Ваш код, то поверьте, у вас нет проблем и все в порядке. Многие "программисты" даже не смогут понять что тут написано. По сабжу мне лень настолько глубоко ковыряться в задаче, но если решение не проходит, то не факт что это ваша проблема, возможно у ребят в среде стоит слишком маленький таймаут на исполнение тестов. Скорость чаще всего теряется на вложенных циклах, у вас есть один for с вложенным while, while опасная штука, которая может приводить к бесконечным зацикливаниям. Проверьте ваш код, чтобы он не мог при определенных условиях переходить к бесконечному исполнению.