MAXimal

добавлено: 11 Jun 2008 11:06
редактировано: 7 Nov 2011 15:45

Нахождение наидлиннейшей возрастающей подпоследовательности

Условие задачи следующее. Дан массив из n чисел: a[0 \ldots n-1]. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.

Формально это выглядит следующим образом: требуется найти такую последовательность индексов i_1 \ldots i_k, что:

 i_1 < i_2 < \ldots < i_k,
 a[i_1] < a[i_2] < \ldots < a[i_k].

В данной статье рассматриваются различные алгоритмы решения данной задачи, а также некоторые задачи, которые можно свести к данной задаче.

Решение за O(n^2): метод динамического программирования

Динамическое программирование — это весьма общая методика, позволяющая решать огромный класс задач. Здесь мы рассмотрим эту методику применительно к нашей конкретной задаче.

Научимся сначала искать длину наидлиннейшей возрастающей подпоследовательности, а восстановлением самой подпоследовательности займёмся чуть позже.

Динамическое программирование для поиска длины ответа

Для этого давайте научимся считать массив d[0 \ldots n-1], где d[i] — это длина наидлиннейшей возрастающей подпоследовательности, оканчивающейся именно в элементе с индексом i. Массив этот (он и есть — сама динамика) будем считать постепенно: сначала d[0], затем d[1] и т.д. В конце, когда этот массив будет подсчитан нами, ответ на задачу будет равен максимуму в массиве d[].

Итак, пусть текущий индекс — i, т.е. мы хотим посчитать значение d[i], а все предыдущие значения d[0] 
\ldots d[i-1] уже подсчитаны. Тогда заметим, что у нас есть два варианта:

  • либо d[i] = 1, т.е. искомая подпоследовательность состоит только из числа a[i].

  • либо d[i] > 1. Тогда перед числом a[i] в искомой подпоследовательности стоит какое-то другое число. Давайте переберём это число: это может быть любой элемент a[j] (j = 0 \ldots i-1), но такой, что a[j] < a[i]. Пусть мы рассматриваем какой-то текущий индекс j. Поскольку динамика d[j] для него уже подсчитана, получается, что это число a[j] вместе с числом a[i] даёт ответ d[j] + 1. Таким образом, d[i] можно считать по такой формуле:

     d[i] = \max_{j=0 \ldots i-1, \atop a[j] < a[i]} ([...]

Объединяя эти два варианта в один, получаем окончательный алгоритм для вычисления d[i]:

 d[i] = \max \Big( 1, \max_{j=0 \ldots i-1, \atop [...]

Этот алгоритм — и есть сама динамика.

Реализация

Приведём реализацию описанного выше алгоритма, которая находит и выводит длину наидлиннейшей возрастающей подпоследовательности:

int d[MAXN]; // константа MAXN равна наибольшему возможному значению n
 
for (int i=0; i<n; ++i) {
	d[i] = 1;
	for (int j=0; j<i; ++j)
		if (a[j] < a[i])
			d[i] = max (d[i], 1 + d[j]);
}
 
int ans = d[0];
for (int i=0; i<n; ++i)
	ans = max (ans, d[i]);
cout << ans << endl;

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

Пока мы лишь научились искать длину ответа, но саму наидлиннейшую подпоследовательность мы вывести не можем, т.к. не сохраняем никакой дополнительной информации о том, где достигаются максимумы.

Чтобы суметь восстановить ответ, помимо динамики d[0 \ldots n-1] надо также хранить вспомогательный массив p[0 \ldots n-1] — то, в каком месте достигся максимум для каждого значения d[i]. Иными словами, индекс p[i] будет обозначать тот самый индекс j, при котором получилось наибольшее значение d[i]. (Этот массив p[] в динамическом программировании часто называют "массивом предков".)

Тогда, чтобы вывести ответ, надо просто идти от элемента с максимальным значением d[i] по его предкам до тех пор, пока мы не выведем всю подпоследовательность, т.е. пока не дойдём до элемента со значением d = 1.

Реализация восстановления ответа

Итак, у нас изменится и код самой динамики, и добавится код, производящий вывод наидлиннейшей подпоследовательности (выводятся индексы элементов подпоследовательности, в 0-индексации).

Для удобства мы изначально положили индексы p[i] = -1: для элементов, у которых динамика получилась равной единице, это значение предка так и останется минус единицей, что чуть-чуть удобнее при восстановлении ответа.

int d[MAXN], p[MAXN]; // константа MAXN равна наибольшему возможному значению n
 
for (int i=0; i<n; ++i) {
	d[i] = 1;
	p[i] = -1;
	for (int j=0; j<i; ++j)
		if (a[j] < a[i])
			if (1 + d[j] > d[i]) {
				d[i] = 1 + d[j];
				p[i] = j;
			}
}
 
int ans = d[0],  pos = 0;
for (int i=0; i<n; ++i)
	if (d[i] > ans) {
		ans = d[i];
		pos = i;
	}
cout << ans << endl;
 
vector<int> path;
while (pos != -1) {
	path.push_back (pos);
	pos = p[pos];
}
reverse (path.begin(), path.end());
for (int i=0; i<(int)path.size(); ++i)
	cout << path[i] << ' ';

Альтернативный способ восстановления ответа

Впрочем, как почти всегда в случае динамического программирования, для восстановления ответа можно не хранить дополнительный массив предков p[], а просто заново пересчитывая текущий элемент динамики и ища, на каком же индексе был достигнут максимум.

Этот способ при реализации приводит к чуть более длинному коду, однако взамен получаем экономию памяти и абсолютное совпадение логики программы в процессе подсчёта динамики и в процессе восстановления.

Решение за O (n \log n): динамическое программирование с двоичным поиском

Чтобы получить более быстрое решение задачи, построим другой вариант динамического программирования за O (n^2), а затем поймём, как можно этот вариант ускорить до O (n \log n).

Динамика теперь будет такой: пусть d[i] (i = 0 \ldots n) — это число, на которое оканчивается возрастающая подпоследовательность длины i (а если таких чисел несколько — то наименьшее из них).

Изначально мы полагаем d[0] = -\infty, а все остальные элементы d[i] = \infty.

Считать эту динамику мы будем постепенно, обработав число a[0], затем a[1], и т.д.

Приведём реализацию этой динамики за O (n^2):

int d[MAXN];
d[0] = -INF;
for (int i=1; i<=n; ++i)
	d[i] = INF;
 
for (int i=0; i<n; i++)
	for (int j=1; j<=n; j++)
		if (d[j-1] < a[i] && a[i] < d[j])
			d[j] = a[i];

Заметим теперь, что у этой динамики есть одно очень важное свойство: d[i-1] \le d[i] для всех i = 1 \ldots n. Другое свойство — что каждый элемент a[i] обновляет максимум одну ячейку d[j].

Таким образом, это означает, что обрабатывать очередное a[i] мы можем за O (\log n), сделав двоичный поиск по массиву d[]. В самом деле, мы просто ищем в массиве d[] первое число, которое строго больше a[i], и пытаемся произвести обновление этого элемента аналогично приведённой выше реализации.

Реализация за O (n \log n)

Воспользовавшись стандартным в языке C++ алгоритмом двоичного поиска upper\_bound (который возвращает позицию первого элемента, строго большего данного), получаем такую простую реализацию:

int d[MAXN];
d[0] = -INF;
for (int i=1; i<=n; ++i)
	d[i] = INF;
 
for (int i=0; i<n; i++) {
	int j = int (upper_bound (d.begin(), d.end(), a[i]) - d.begin());
	if (d[j-1] < a[i] && a[i] < d[j])
		d[j] = a[i];
}

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

По такой динамике тоже можно восстановить ответ, для чего опять же помимо динамики d[i] также надо хранить массив "предков" p[i] — то, на элементе с каким индексом оканчивается оптимальная подпоследовательность длины i. Кроме того, для каждого элемента массива a[i] надо будет хранить его "предка" — т.е. индекс того элемента, который должен стоять перед a[i] в оптимальной подпоследовательности.

Поддерживая эти два массива по ходу вычисления динамики, в конце будет нетрудно восстановить искомую подпоследовательность.

(Интересно отметить, что применительно к данной динамике ответ можно восстанавливать только так, через массивы предков — а без них восстановить ответ после вычисления динамики будет невозможно. Это один из редких случаев, когда к динамике неприменим альтернативный способ восстановления — без массивов предков).

Решение за O (n \log n): структуры данных

Если приведённый выше способ за O (n \log n) весьма красив, однако не совсем тривиален идейно, то есть и другой путь: воспользоваться одной из известных простых структур данных.

В самом деле, давайте вернёмся к самой первой динамике, где состоянием являлась просто текущая позиция. Текущее значение динамики d[i] вычисляется как максимум значений d[i] среди всех таких элементов j, что a[j] < a[i].

Следовательно, если мы через t[] обозначим такой массив, в который будем записывать значения динамики от чисел:

 t[a[i]] = d[i],

то получается, что всё, что нам надо уметь — это искать максимум на префиксе массива t: t[0 \ldots a[i]-1].

Задача поиска максимума на префиксах массива (с учётом того, что массив может меняться) решается многими стандартными структурами данных, например, деревом отрезков или деревом Фенвика.

Воспользовавшись любой такой структурой данных, мы получим решение за O (n \log n).

У этого способа решения есть явные недостатки: по длине и сложности реализации этот путь будет в любом случае хуже, чем описанная выше динамика за O (n \log n). Кроме того, если входные числа a[i] могут быть достаточно большими, то скорее всего их придётся сжимать (т.е. перенумеровывать от 0 до n-1) — без этого многие стандартные структуры данных работать не смогут из-за высокого потребления памяти.

С другой стороны, у данного пути есть и преимущества. Во-первых, при таком способе решения не придётся задумываться о хитрой динамике. Во-вторых, этот способ позволяет решать некоторые обобщения нашей задачи (о них см. ниже).

Смежные задачи

Приведём здесь несколько задач, тесно связанных с задачей поиска наидлиннейшей возрастающей подпоследовательности.

Наидлиннейшая неубывающая подпоследовательность

Фактически, это та же самая задача, только теперь в искомой подпоследовательности допускаются одинаковые числа (т.е. мы должны найти нестрого возрастающую подпоследовательность).

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

Количество наидлиннейших возрастающих подпоследовательностей

Для решения этой задачи можно использовать самую первую динамику за O (n^2) либо подход с помощью структур данных для решения за O (n \log n). И в том, и в том случае все изменения заключаются только в том, что помимо значения динамики d[i] надо также хранить, сколькими способами это значение могло быть получено.

По всей видимости, способ решения через динамику за O (n \log n) к данной задаче применить невозможно.

Наименьшее число невозрастающих подпоследовательностей, покрывающих данную последовательность

Условие таково. Дан массив из n чисел a[0 \ldots n-1]. Требуется раскрасить его числа в наименьшее число цветов так, чтобы по каждому цвету получалась бы невозрастающая подпоследовательность.

Решение. Утверждается, что минимальное количество необходимых цветов равно длине наидлиннейшей возрастающей подпоследовательности.

Доказательство. Фактически, нам надо доказать двойственность этой задачи и задачи поиска наидлиннейшей возрастающей подпоследовательности.

Обозначим через x длину наидлиннейшей возрастающей подпоследовательности, а через y — искомое наименьшее число невозрастающих подпоследовательностей. Нам надо доказать, что x=y.

С одной стороны, понятно, почему не может быть y<x: ведь если у нас есть x строго возрастающих элементов, то никакие два из них не могли попасть в одну невозрастающую подпоследовательность, а, значит, y \ge x.

Покажем теперь, что, наоборот, y не может быть > x. Докажем это от противного: предположим, что y > x. Тогда рассмотрим любой оптимальный набор из y невозрастающих подпоследовательностей. Преобразуем этот набор таким образом: пока есть две таких подпоследовательности, что первая начинается раньше второй, но при этом первая начинается с числа, больше либо равного чем начало второй — отцепим это стартовое число от первой подпоследовательности и прицепим в начало второй. Таким образом, через какое-то конечное число шагов у нас останется y подпоследовательностей, причём их стартовые числа будут образовывать возрастающую подпоследовательность длины y. Но y > x, т.е. мы пришли к противоречию (ведь не может быть возрастающих подпоследовательностей длиннее x).

Таким образом, в самом деле, y = x, что и требовалось доказать.

Восстановление ответа. Утверждается, что само искомое разбиение на подпоследовательности можно искать жадно, т.е. идя слева направо и относя текущее число в ту подпоследовательность, которая сейчас заканчивается на минимальное число, больше либо равное текущему.

Задачи в online judges

Список задач, которые можно решить по данной тематике: