Задача 76271
|
|
 |
Условие
(из книги Д. Гриса) Дана последовательность целых чисел x[1],...,x[n]. Найти максимальную длину её возрастающей подпоследовательности (число действий порядка n log n).Решение
Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим её k) также и числа u[1], ..., u[k], где u[i] — минимальный из последних членов возрастающих подпоследовательностей длины i. Очевидно, u[1]≤...≤u[k]. При добавлении нового члена в x значения u и k корректируются. n1 := 1; k := 1; u[1] := x[1];
{инвариант: k и u соответствуют данному выше описанию}
while n1 <> n do begin
| n1 := n1 + 1;
| ...
| {i - наибольшее из тех чисел отрезка 1..k, для
| которых u[i] < x[n1]; если таких нет, то i=0 }
| if i = k then begin
| | k := k + 1;
| | u[k+1] := x[n1];
| end else begin {i < k, u[i] < x[n1] <= u[i+1] }
| | u[i+1] := x[n1];
| end;
end;
Фрагмент ... использует идею двоичного поиска;
в инварианте условно полагаем u[0] равным минус
бесконечности, а u[k+1] — плюс бесконечности. Наша
цель:
u[i] < x[n1]≤u[i+1].
i:=0; j:=k+1;
{u[i] < x[n1] <= u[j], j > i}
while (j - i) <> 1 do begin
| s := i + (j-i) div 2; {i < s < j}
| if x[n1] <= u[s] then begin
| | j := s;
| end else begin {u[s] < x[n1]}
| | i := s;
| end;
end;
{u[i] < x[n1] <= u[j], j-i = 1}
Замечание. Более простое (но не минимальное) индуктивное
расширение получится, если для каждого i хранить
максимальную длину возрастающей подпоследовательности,
оканчивающейся на x[i]. Это расширение приводит
к алгоритму с числом действий порядка
n2. Есть
и другой изящный алгоритм с квадратичным временем работы
(сообщил М.В.Вьюгин):
найти максимальную общую подпоследовательность исходной
последовательности и отсортированной
последовательности с помощью предыдущей задачи.
