Дана последовательность целых чи- сел 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 u[s] >= x[n1] 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]. Это расширение приводит к алгоритму с числом действий по- рядка n*n  8  Комментарии к статье  8 8  Обсудить в чате