LIS - Алгоритм наибольшей возрастающей подпоследовательности в PHP O(nlogn)

Question

Я нигде не могу найти решения для моей проблемы:(. Может кто-нибудь помочь мне и найти (или написать) этот алгоритм с комментариями? Я не могу сделать это сам. Я потратил на это по крайней мере 3 часа и ничего.

Большое спасибо!

Answer 1

Сохраняет вектор 'v[x] = y', где y - наименьший элемент исходной последовательности, который дает самую длинную увеличивающуюся подпоследовательность длины x. Первоначально у вас есть только v[0] = -inf,

Пройдите последовательность для элемента aпосмотрите в векторе v используя бинарный поиск. Не найдешь a точно, но самый большой x такой, что v[x] <= a (<если оно строго увеличивается). Таким образом, самая длинная возрастающая подпоследовательность, которая заканчивается на воле, будет иметь длину x+1, Теперь обновите v[x+1] быть (это не может быть меньше, чем, иначе ваш поиск должен иметь возврат x+1), вам может понадобиться расширить вектор.

Длина LIS - это размер вектора. Отслеживайте, какие позиции вы использовали, если вам нужно восстановить решение.