7.2 Наибольшая возрастающая подпоследовательность¶
Рассмотрим задачу поиска наибольшей возрастающей подпоследовательности в массиве из n элементов. Это подпоследовательность максимальной длины, которая идет слева направо, и каждый следующий элемент в ней строго больше предыдущего.
Например, для массива:
5 1 4 2 6 3 7 0
0 1 2 3 4 5 6 7
одна из наибольших возрастающих подпоследовательностей имеет длину 4:
1 4 6 7
Обозначим через length(k) длину наибольшей возрастающей подпоследовательности, которая заканчивается в позиции k. Если мы вычислим все значения length(k) для 0 ≤ k ≤ n-1, то сможем найти и общую длину ответа — это просто максимум среди них.
Для приведенного массива значения могут быть такими:
length(0) = 1
length(1) = 1
length(2) = 2
length(3) = 2
length(4) = 3
length(5) = 3
length(6) = 4
length(7) = 1
Например, length(6) = 4, потому что наилучшая возрастающая подпоследовательность, оканчивающаяся в позиции 6, содержит четыре элемента.
Чтобы вычислить length(k), нужно найти такую позицию i < k, что:
array[i] < array[k],- значение
length(i)максимально возможно.
Тогда можно дописать array[k] в конец оптимальной подпоследовательности, оканчивающейся в i, и получить:
Если подходящей позиции i не существует, то
то есть подпоследовательность состоит только из элемента array[k].
Поскольку все значения функции выражаются через меньшие индексы, здесь естественно применяется динамическое программирование.
Ниже приведена реализация, где значения функции хранятся в массиве length:
for (int k = 0; k < n; k++) {
length[k] = 1;
for (int i = 0; i < k; i++) {
if (array[i] < array[k]) {
length[k] = max(length[k], length[i] + 1);
}
}
}
Этот алгоритм работает за O(n^2), потому что использует два вложенных цикла.
При этом существует и более быстрый способ вычисления длины наибольшей возрастающей подпоследовательности — за O(n log n). Он основан уже не на прямом хранении всех length(k), а на поддержании специальной структуры минимально возможных хвостов для подпоследовательностей каждой длины.
В этом разделе мы ограничились классическим динамическим решением за O(n^2), потому что оно напрямую показывает идею перехода между подзадачами и хорошо иллюстрирует сам подход динамического программирования.