Урок №8

Урок №8. "Возрастающая подпоследовательность"

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

- Задана последовательность чисел a1, a2, …, an

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

1 5 3 7 1 4 10 15

Перебор?

- Число различных подпоследовательностей: (2n – 1)

- Можно применять для n ≤ 20

1 2 3

1

2

3

1 2

1 3

2 3

1 2 3

Разбиение на подзадачи

Идея: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai

Попробуйте построить рекуррентную формулу

Более точно: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai, последний элемент в которой - ai

Рекуррентная формула

d[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в ai

Считается, что максимум равен нулю, если таких индексов j нет

Начальные условия

Можно сделать немного проще

Считаем, что в начало добавлен a0=–∞, а d[0] = 0

Теперь можно не делать никаких предположений, так как всегда найдется некоторый индекс j

Шаг 1

Шаг 2

Шаг 3

Шаг 4

Шаг 5

Шаг 6

Шаг 7

Шаг 8

Шаг 9

Программа

d[0] := 0;

for i := 1 to n do begin

max := 0;

for j := 1 to i – 1 do begin

if (a[j] < a[i]) and

(d[j] > max) then begin

max := d[j];

end;

end;

d[i] := max + 1;

end;

Где находится длина L наибольшей возрастающей подпоследовательности?

L := 0;

pos := -1;

for i := 1 to n do begin

if (d[i] > max) then begin

max := d[i];

pos := i;

end;

end;

Вычисление с сохранением информации для восстановления ответа

d[0] := 0;

prev[0] := -1;

for i := 1 to n do begin

max := 0;

bestj := -1;

for j := 1 to i – 1 do begin

if (a[j] < a[i]) and

(d[j] > max) then begin

max := d[j];

bestj := j;

end;

end;

d[i] := max + 1;

prev[i] := bestj;

end;

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

procedure restore(i : integer);

begin

if (i > 0) then begin

restore(prev[i]);

write(a[i]);

end;

end;

Пример

1 3 4 10 15

Время работы этого алгоритма – O(n2)

Возникает вопрос а можно ли быстрее? Похоже, что от вычисления d[i] никуда не деться. Попробуем вычислять d[i] быстрее:

Пусть last[i] – минимальное последнее число в возрастающей подпоследовательности длины i

Массив Last является неубывающим, действительно, пусть i < j, но last[i] > last[j]

Из подпоследовательности длины i можно сделать подпоследовательность длины j, поэтому last[j] ≤ last[i] (last[j] – минимальный, last[i] – некоторый)

1. Находим место в массиве last, на которое следует поставить a[i] – такую позицию j, что last[j-1] < a[i] ≤ last[j]

2. Это означает, что максимальная длина подпоследовательности, которая заканчивается в a[i] есть j (d[i] = j)

3. Позицию j надо искать с помощью двоичного поиска

Время работы алгоритма – O(nlogn)

Практическая работа

Продумать, как сохранять информацию для восстановления ответа Реализовать этот алгоритм | Самостоятельная работа