Самая длинная возрастающая последовательность


Описание задачи

Задав целочисленный массив nums, верните длину самой длинной строго возрастающей подпоследовательности.

Подпоследовательность — это последовательность, которая может быть получена из массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Например, [3,6,2,7] является подпоследовательностью массива [0,3,1,6,2,2,7].

Концепция

Метод грубой силы применяется путем простого составления всех возможных возрастающих подпоследовательностей от нулевого индекса, затем сохранения всех их в памяти и возвращения самого длинного из списков-кандидатов. Этот подход имеет временную сложность O(n^2), где n — длина массива. Это связано с n количеством перестановок от нулевого индекса, причем каждая перестановка требует в худшем случае n количества проверок (для формирования подпоследовательности).

Из метода перебора очевидно, что возможны улучшения, если мы примем во внимание, что мы хотим, чтобы элементы в подпоследовательности были настолько малы, насколько это возможно, прежде чем мы увеличим другой элемент. Например: мы, очевидно, отбросим 3 в [0,3] для следующего элемента, если он меньше 3, поскольку это увеличивает диапазон чисел, которые мы можем получить для следующего большего элемента, т.е. [0,1] лучше, чем [0,3]. Если мы применим ту же концепцию не только к последнему числу в нашей текущей подпоследовательности, но и ко всем числам в подпоследовательности, мы сможем увеличить диапазон возможных чисел во всех позициях подпоследовательности. Таким образом, мы будем создавать и поддерживать самую длинную возрастающую подпоследовательность на протяжении всего цикла. Наш алгоритм будет работать следующим образом: 1. Если следующий элемент больше, чем последний элемент нашей подпоследовательности, добавляем его в подпоследовательность. 2. В противном случае находим наибольшее число в подпоследовательности, которое может заменить элемент, так, чтобы число было меньше элемента и замена числа на элемент сохраняла условие возрастания подпоследовательности. Я знаю, что это звучит запутанно, пример лучше проиллюстрирует концепцию.

Обратите внимание на пару вещей из этого примера. Во-первых, конечная самая длинная возрастающая подпоследовательность не является существующей допустимой подпоследовательностью в nums. К счастью, в задаче требуется только вернуть длину подпоследовательности. Во-вторых, мы гарантируем существование действительной подпоследовательности в прошлом после замены элемента подпоследовательности на следующий элемент, если только следующий элемент меньше предыдущего. Пример: На 5-й итерации получается подпоследовательность [1,2,6], хотя она не выводима из nums, мы точно знаем, что такая допустимая подпоследовательность существовала, [4,5,6] с третьей итерации. Отсюда следует, что существование [1,2,6,7,8], несуществующей подпоследовательности, гарантирует существование в прошлом действительной подпоследовательности, удовлетворяющей нашему условию приращения, в данном примере это [4,5,6,7,8]. Эти два наблюдения показывают нам, что алгоритм не производит ложных подпоследовательностей. Чтобы проиллюстрировать возможности алгоритма, рассмотрим следующий пример.

Обратите внимание, что, находя наименьшее возможное число, занимающее каждый индекс, мы максимизируем диапазон чисел, которые мы можем найти. Хотя мы могли бы создать самую длинную возрастающую подпоследовательность аналогично нашим элементам на 3-й итерации, [4,5,6], минимизируя элементы, например, на 6-й итерации, мы увеличиваем потенциал нашей подпоследовательности, поскольку следующий элемент должен быть больше 3, а не 6. Поймите, что мы можем поместить 3 только на 6-й итерации, потому что элемент перед 3 — 2, а не 5, что подчеркивает важность минимизации числа во всех индексах из-за эффекта домино.

Алгоритм сохраняет текущую самую длинную возрастающую подпоследовательность на каждой итерации и выполняет итерацию один раз по всему списку. Чтобы найти позицию следующего элемента в текущей подпоследовательности, мы выполняем двоичный поиск. Таким образом, временная сложность алгоритма составляет O(n*log(n)).

Реализация

Мы создаем переменную tmp для отслеживания текущей самой длинной возрастающей подпоследовательности. Затем мы перебираем каждый элемент в nums. На каждой итерации мы проверяем, будет ли этот элемент при вставке самым большим элементом или нет. Эта проверка выполняется функцией bisect_left, которая принимает отсортированный список tmp и число x и возвращает позицию x, занимаемую в tmp таким образом, чтобы tmp оставался отсортированным. Функция bisect_left использует бинарный поиск. Если элемент является самым большим, то bisect_left вернет последний индекс вновь добавленного a, который равен len(temp). Как мы установили, если элемент, n, является самым большим, мы добавляем его, в противном случае, мы находим наименьший элемент, который больше n в tmp и заменяем его на n, bisect_left возвращает индекс для замены. Наконец, мы возвращаем переменную.

def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp,n)
            if x == len(tmp):
                tmp.append(n)
            else:
                tmp[x] = n
        return len(tmp)
Вход в полноэкранный режим Выход из полноэкранного режима

Реальное применение алгоритма длиннейшей возрастающей последовательности

Часть программы Maximum Unique Match Finder для выравнивания целых геномов.

Примечания

Удивительно, но алгоритм поиска самой длинной возрастающей подпоследовательности, а не просто ее длины, также имеет временную сложность O(n*log(n)). Алгоритм вдохновлен карточной игрой Patience или Klondike. Вот отличный ресурс, где можно узнать о Patience Sort. Забавно, но во время базового курса подготовки полицейских я сидел рядом со своим другом, который играл в «Клондайк» на протяжении всего занятия, это была одна из немногих игр, доступных на выданных нам ноутбуках.

Оцените статью
devanswers.ru
Добавить комментарий