Delphi World - Найти максимальную длину возрастающей подпоследовательности целых чисел
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Найти максимальную длину возрастающей подпоследовательности целых чисел

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

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования