300_Longest_Increasing_Subsequence

Решение задачи 300. Longest Increasing Subsequence

Дан массив целых чисел nums[] длины n. Требуется найти самую длинную строго восходящую подпоследовательнось его элементов. То есть, каждый следующий элемент подпоследовательности должен быть строго больше предыдущего. При этом элементы не обязательно следуют непосредственно друг за другом и являются соседними, однако относительное их расположение в подпоследовательности и исходном массиве одинаково. То есть, меньший элемент предшествует большему и в подпоследовательности и в исходном массиве.

Для решения задачи подходят принципы динамического программирования. Что, если бы на момент рассмотрения очередного элемента массива i нам было бы известно на каких элементах nums[j...] заканчиваются уже найденные восходящие подпоследовательности подмассива [0, i - 1]?

Заведем массив dp_[] длины n, где для каждой позиции j от 0 до n - 1 dp_[j] содержит значение последнего элемента восходящей подпоследовательности длины j. Согласно определению строго восходящей подпоследовательности элемент, предшествующий последнему будет строго меньше последнего. То есть dp_[j - 1] < dp_[j]. Одновременно с этим элемент dp_[j - 1] является последним элементом подпоследовательности длины j - 1. Таким образом, для любого j от 0 до n - 1 dp_[j - 1] будет меньше dp_[j], а массив dp_[] будет поддерживаться отсортированным по возрастанию. Это свойство позволяет пользоваться бинарным поиском, и в массиве dp_[] с помощью метода std::upper_bound() можно найти место для любого элемента массива nums[]. Так как по условию мы ищем строго восходящую подпоследовательность, то перед размещением в массиве dp_ элемента массива nums[] надо убедиться, что он не равен предшествующему элементу. Равенство с последующим проверять не нужно - алгоритм std::upper_bound гарантирует возврат итератора элемента строго большего искомому, или end(), если такой элемент отсутствует.

Теперь об алгоритме по порядку:

• В массиве dp_[] для j от 0 до n - 1 dp_[j] будет равен значению элемента из массива nums[], на котором заканчивается восходящая подпоследовательность длины j.
• Инициализируем массив dp_[] длины n значением INT_MAX. Для корректной работы алгоритма элементы массива nums[] должны быть меньше этого значения.
• Инициализируем начальный элемент dp_[0] = INT_MIN - базовый случай. В непустом массиве nums[] не может существовать восходящей подпоследовательности нулевой длины.
• Заведем переменную length для сохранения длины максимальной восходящей подпоследовательности.
• Для i от 0 до n - 1 для каждого элемента nums[i] бинарным поиском std::upper_bound() по массиву dp_[] ищем позицию j перед которой мы могли бы разместить элемент nums[i], при этом проверяем, что dp_[j - 1] < nums[i]. Если условие выполняется, присваиваем dp_[j] = nums[i]. Обновляем переменную length = std::max(length, j).
• Возвращаем ответ - length.

Моя реализация здесь.