Дана последовательность целых чи- сел 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.