LIS — Алгоритм наибольшей возрастающей подпоследовательности в PHP O (nlogn)
Я нигде не могу найти решения для моей проблемы :(.
Может кто-нибудь помочь мне и найти (или написать) этот алгоритм с комментариями?
Я не могу сделать это сам. Я потратил на это как минимум 3 часа и ничего.
Большое спасибо!
Решение
Сохраняет вектор ‘v [x] = y’, где y — наименьший элемент исходной последовательности, который дает самую длинную увеличивающуюся подпоследовательность длины x. Первоначально у вас есть только v[0] = -inf,
Пройдите последовательность для элемента aпосмотрите в векторе v используя бинарный поиск. Не найдешь a точно, но самый большой x такой, что v[x] <= a (< если оно строго увеличивается). Таким образом, самая длинная возрастающая подпоследовательность, которая заканчивается на воле, будет иметь длину x+1, Теперь обновите v[x+1] быть (это не может быть меньше, чем, иначе ваш поиск должен иметь возврат x+1), вам может понадобиться расширить вектор.
Длина LIS — это размер вектора. Отслеживайте, какие позиции вы использовали, если вам нужно восстановить решение.
Другие решения
Других решений пока нет …