Продолжаю цикл разбора алгоритмов по курсу, который я проходил на stepic.org. Сегодня рассмотрим достаточно сложную задачу.

Дано целое число $%1 \le n \le 10^5$% и массив $%A[1...n]$%, содержащий неотрицательные целые числа, не превосходящие $%10^9$%. Найдите наибольшую невозрастающую подпоследовательность в $%A$%. В первой строке выведите её длину $%k$%, во второй — её индексы $%1\le i_1 \lt i_2\lt \ldots \lt i_k \le n$% (таким образом, $%A[i_1] \ge A[i_2] \ge \ldots \ge A[i_n]$%)

Sample Input:
5
5 3 4 4 2

Sample Output:
4
1 3 4 5

Решение этой задачи методом динамического программирования со временем исполнения $%O(n^2)$% я написал достаточно быстро, и алгоритм решения на Python выглядит так:

def main():
    # Прочитаем исходные данные из консоли
    n = int(input())
    arr = [int(i) for i in input().split(' ')]
    # Создадим вспомогательный список, в котором будем хранить решения
    lds = [1]*(n)
    # В цикле посчитаем с конца, сколько элементов подпоследовательности являются невозрастающими
    # Нам нужно выполнить расчет для каждого элемента последовательности, т.е. время решения O(n^2)
    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if arr[i] >= arr[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1
    # Выведем максимальный элемент, это будет количество элементов в подпоследовательности
    print(max(lds))
  
    # Восстановим решение по рассчитанным данным
    for i in range(n):
        if lds[i] == max_lds:
            print(i + 1, end=' ')
            max_lds = max_lds - 1


if __name__ == "__main__":
    main()

Однако это решение не удалось сдать, т.к. при числах, приближающимся к $%10^9$% алгоритм начинал работать непозволительно долго. Требовалось найти решение, которое работает быстрее.

Пришлось немного погуглить и решение с временем работы - $%O(n log n)$% нашлось. Для решения моей задачи алгоритм из статьи понадобилось немного модифицировать.
Я сделал реверс заданной последовательности, а также добавил увеличение значения минимума при $%x[M[mid]] = x[i]$%.

Вот такой пример решения на Python у меня получился:

def longest_subseq():
    # Прочитаем исходные данные из консоли
    n = int(input())
    x = [int(i) for i in input().split(' ')]
    P = [0]*n
    M = [0]*(n + 1)
    L = 0
    x = x[::-1]
    for i in range(n):
        lo = 1
        hi = L
        while lo <= hi:
            mid = (lo + hi) // 2
            if x[M[mid]] < x[i]:
                lo = mid + 1
            elif x[M[mid]] == x[i]:
                lo += 1
            else:
                hi = mid - 1
        newL = lo
        P[i] = M[newL - 1]
        if newL > L:
            M[newL] = i
            L = newL
        elif x[i] < x[M[newL]]:
            M[newL] = i
    
    # Восстановим решение по рассчитанным данным
    re = [0]*L
    k = M[L]
    for i in range(L-1, -1, -1):
        re[i] = n - k
        k = P[k]
    print(len(re))
    print(' '.join(map(str,re[::-1])))

if __name__ == "__main__":
    longest_subseq()

Наверно можно оптимизировать это решение, не выполняя реверс, но кажется от этого алгоритм потеряет наглядность, так как нужно будет выполнять обратный цикл и сравнивать элементы немного иначе.