Наибольшая возрастающая подпоследовательность

Дан массив. Надо выбрать из него как можно больше элементов, идущих слева направо и строго возрастающих. Выбирать можно не подряд.

Задача важна не сама по себе: её решение — образец того, как динамика ускоряется сменой состояния.

Квадратичное решение

Состояние: $d[i]$ — длина наибольшей возрастающей подпоследовательности, кончающейся ровно в элементе $i$.

Слово «ровно» здесь несущее. Если определить $d[i]$ как «на префиксе до $i$», переход не выпишется: неизвестно, каким элементом кончается найденная подпоследовательность, а значит, непонятно, можно ли к ней приписать $a_i$.

vector<int> d(n, 1);
int answer = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
        if (a[j] < a[i]) d[i] = max(d[i], d[j] + 1);
    answer = max(answer, d[i]);
}

Сложность $O(n^2)$. Ответ — максимум по всей таблице, а не $d[n-1]$: подпоследовательность вовсе не обязана кончаться последним элементом.

Решение за n log n

Смена точки зрения: вместо «какой длины подпоследовательность кончается здесь» будем хранить «каким наименьшим числом может кончаться подпоследовательность длины $k$».

Массив tail: tail[k] — минимально возможный последний элемент среди всех возрастающих подпоследовательностей длины $k + 1$. Он строго возрастает — иначе более длинную можно было бы укоротить и получить противоречие.

Раз массив упорядочен, место очередного элемента ищется бинарным поиском.

vector<int> tail;
for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x);        // удлинили ответ
    else *it = x;                                   // улучшили окончание
}
cout << tail.size();

Проверено: на 3000 случайных массивах до 12 элементов оба решения совпадают с полным перебором подмножеств.

Важно понимать, что tail — не сама подпоследовательность. Это набор лучших окончаний разной длины; выводить его как ответ нельзя. Длина у него верная, содержимое — нет.

Замер

Разница не академическая. g++ -O2, случайные массивы:

$n$	$O(n^2)$	$O(n \log n)$
10 000	120 мс	0,3 мс
50 000	3054 мс	1,8 мс
100 000	~12 с	3,7 мс
200 000	~49 с	7,7 мс

Значения для последних двух строк — пересчёт по квадратичному росту, замерять их не стали. Вывод обычный: при $n \le 5000$ пишите квадрат, он проще и его труднее испортить; при $n \ge 10^5$ выбора нет.

Строгое и нестрогое возрастание

Здесь ошибаются чаще, чем во всём остальном решении. Разница — одна буква в вызове библиотечной функции.

нужно	сравнение в квадрате	функция в быстром решении
строго возрастающая	a[j] < a[i]	lower_bound
неубывающая	a[j] <= a[i]	upper_bound

Проверить себя можно за секунду: массив из пяти одинаковых чисел. Для строгого возрастания ответ 1, для неубывания — 5. Если ваш код на таком массиве даёт не то, что просит условие, — вы взяли не ту функцию.

Для наибольшей убывающей подпоследовательности не надо писать второй код: разверните массив или поменяйте знаки. Второй раз выписывать ту же логику с перевёрнутыми сравнениями — верный способ ошибиться.

Восстановление

В квадратичном решении — обычным массивом предков, как показано в соответствующей статье.

В быстром решении сложнее: tail перезаписывается и историю не хранит. Приём такой: запоминаем для каждого элемента позицию, на которую он встал в tail, и предка — элемент, стоявший в tail на позицию левее в тот момент. Дальше восстановление обычное, по предкам.

vector<int> tail, tailIndex, from(n, -1), position(n);
for (int i = 0; i < n; i++) {
    int k = lower_bound(tail.begin(), tail.end(), a[i]) - tail.begin();
    if (k > 0) from[i] = tailIndex[k - 1];
    position[i] = k;
    if (k == (int)tail.size()) { tail.push_back(a[i]); tailIndex.push_back(i); }
    else { tail[k] = a[i]; tailIndex[k] = i; }
}

Стартовать восстановление надо от элемента, у которого position максимальна.

Проверено: на 20 000 массивах до 14 элементов восстановленная так последовательность возрастает, является подпоследовательностью исходной и имеет длину, равную ответу быстрого решения.

Где это встречается не под своим именем

Задача про НВП редко называется своим именем в условии. Признаки:

• «наибольшее число ящиков, вложенных друг в друга», «матрёшки», «конверты» — сортировка по одному размеру, НВП по второму;
• «минимальное число невозрастающих последовательностей, на которые разбивается массив» — по теореме Дилворта это длина НВП. Проверено перебором раскрасок на 4000 массивах до девяти элементов;
• «наименьшее число элементов, которые надо удалить, чтобы массив стал возрастающим» — это $n$ минус НВП;
• «наибольшая общая подпоследовательность двух перестановок» — сводится к НВП заменой элементов на их позиции.

Последний случай особенно полезен: НОП в общем виде считается за $O(nm)$, а для перестановок — за $O(n \log n)$ именно через это сведение. Проверено: на 5000 пар перестановок до восьми элементов длина НОП совпала с длиной НВП после замены элементов на позиции.