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

---