Наибольшая возрастающая подпоследовательность (НВП) за $O(N \log N)$
Ранее мы обсуждали решение задачи LIS с использованием динамического программирования, которое работает за . Мы пришли к формуле = длина самой длинной возрастающей подпоследовательности, заканчивающейся на (где включен в последовательность).
Чтобы добиться лучшего результата, чем , нам нужно выбрать другое состояние для нашего . Пусть = наименьший элемент, на котором заканчивается некоторая возрастающая последовательность длины . Изначально массив выглядит так:
Затем мы обрабатываем элементы массива один за другим и обновляем наш . При обработке нам нужно проверить для каждого , возможно ли расширить последовательность длины , используя . Формально, для каждого проверяем, если и выбираем наименьшее , для которого это верно, и устанавливаем равным этому значению. Легко увидеть, почему выбор наименьшего такого является оптимальным.
Обработка 4: Число 4 является первым элементом, поэтому это наименьшее число, на котором заканчивается подпоследовательность длины 1.
Обработка 1: Число 1 может заменить 4 в массиве DP, так как 1 меньше и также заканчивает подпоследовательность длины 1.
Обработка 3: Число 3 больше 1, поэтому оно увеличивает длину подпоследовательности до 2. Теперь это наименьшее число, заканчивающее подпоследовательность длины 2.
Обработка 2: Число 2 меньше 3 и больше 1, поэтому оно заменяет 3 в массиве DP как конечный элемент подпоследовательности длины 2.
Обработка 5: Число 5 увеличивает возрастающую последовательность; теперь это наименьшее число, которое заканчивает подпоследовательность длины 3.
После этих шагов массив указывает, что самая длинная возрастающая подпоследовательность имеет длину 3, что является наибольшим индексом с значением меньше .
Основываясь на этих наблюдениях, мы можем найти такой с помощью бинарного поиска. Мы хотим найти первый элемент в , который строго больше . Это занимает не более , таким образом, мы получаем общую сложность .
Вернемся к первому состоянию , которое мы использовали для решения этой задачи.
И давайте определим новый массив , такой что .
Теперь, чтобы вычислить , нам нужно найти максимальное значение в префиксе массива :
Это можно легко сделать с помощью Деревьев отрезков/Деревьев Фенвика.
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> dp(n+1, INF);
dp[0] = -INF;
for (int i = 0; i < n; i++) {
for (int l = 1; l <= n; l++) {
if (dp[l - 1] < a[i] && a[i] < dp[l])
dp[l] = a[i];
}
}
int ans = 1;
for (int l = 1; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n + 1, INF);
dp[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(dp.begin(), dp.end(), a[i]) - d.begin();
if (dp[l - 1] < a[i] && a[i] < dp[l])
dp[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (dp[l] < INF)
ans = l;
}
return ans;
}