Алгоритм Робинсона-Шенстеда для нахождения самой длинной возрастающей подпоследовательности заключается в последовательном формировании вспомогательной последовательности m, длина которой равна длине обнаруженной подпоследовательности. 3

Элемент последовательности mi говорит о том, что существует монотонная подпоследовательность, в которой элемент исходной последовательности, равный mi, занимает позицию номер i. 3

Алгоритм обрабатывает элементы последовательности по порядку, сохраняя самую длинную возрастающую подпоследовательность, найденную на данный момент. 1 Для этого используются массивы и бинарный поиск. 1

После выполнения алгоритма длина L будет равна длине искомой подпоследовательности, а сами элементы можно получить, разворачивая P рекурсивно из элемента index. 2