Требуется найти в массиве чисел возрастающую подпоследовательность наибольшей длины за время O(n log n).
Статья не содержит ничего нового. Просто еще одна реализация классического алгоритма на Delphi.
Сначала приведем описание алгоритма на пальцах. Назовем наилучшей цепочкой длины L подпоследовательность, содержащую наименьший последний элемент среди всех возрастающих подпоследовательностей длины L. Мы будем искать наилучшие цепочки всех возможных длин последовательно: сначала только для первого элемента массива (ясно, что она состоит из этого элемента), затем для двух первых элементов, трех, и т.д. Понятно, что на каждом шагу алгоритма либо будет найдена наилучшая цепочка большей длины, либо будет “улучшена” ровно одна из найденных ранее. В процессе вычислений мы будем запоминать и корректировать последние элементы всех наилучших цепочек. Будем использовать двоичный поиск корректируемого элемента, т.к. у более длинных наилучших цепочек последний элемент должен быть больше. На каждом шагу алгоритма мы также будем запоминать позицию очередного элемента исходного массива в наилучшей цепочке, чтобы потом вывести наибольшую возрастающую подпоследовательность.
type
TNums= array of integer;
TIndex= array of integer;
function LongestIncreasingSubsequence1(const Nums: TNums): TIndex;
var
NumPos: TIndex; //NumPos[i] - позиция числа Nums[i] в цепочке
Last : TIndex; //Last[i] - индекс в массиве Nums последнего числа цепочки длины i+1
MaxPos: integer; //текущая верхняя граница массива Last
i, Left, Right, Cur, NumCount: integer;
begin;
NumCount:=Length(Nums);
if NumCount=0 then SetLength(Result,0)
else begin;
SetLength(NumPos, NumCount);
SetLength(Last, NumCount);
MaxPos:=-1;
for i:=0 to NumCount-1 do begin;
Left:=0;
Right:=MaxPos;
while Left<=Right do begin;
Cur:=(Left+Right) shr 1;
if Nums[i]<=Nums[Last[Cur]] then Right:=Cur-1
else Left :=Cur+1;
end;
NumPos[i]:=Left;
Last[Left]:=i;
if MaxPos<Left then MaxPos:=Left;
end;
SetLength(Result, MaxPos+1);
i:=NumCount;
while true do begin;
dec(i);
if NumPos[i]=MaxPos then begin;
Result[MaxPos]:=i;
dec(MaxPos);
if MaxPos<0 then break;
end;
end;
end;
end;Если вместо позиции числа в цепочке запоминать номер предыдущего числа, то можно упростить вывод результата. Соответствующий алгоритм впервые предложил M. L. Fredman в 1975 году. Алгоритм и его более формальное описание с небольшими косметическими изменениями приводятся ниже.
Пусть Numbers[0..NumCount-1] — массив, содержащий элементы исходной последовательности. Тогда на i-том шагу алгоритма после обработки элемента Numbers[i] значение MaxPos+1 равно длине наибольшей возрастающей подпоследовательности для массива Numbers[0..i], а текущее состояние процесса вычислений хранится в двух одномерных массивах:
- Last[0..MaxPos], каждый элемент которого Last[j] хранит положение k наименьшего элемента Numbers[k] такого, что существует возрастающая подпоследовательность длины j, заканчивающаяся элементом Numbers[k];
- Prev[0..i], каждый элемент которого Prev[k] хранит положение предшественника Numbers[k] в наибольшей возрастающей подпоследовательности, заканчивающейся элементом Numbers[k].
Заметим, что если существует возрастающая подпоследовательность длины i+1, заканчивающаяся элементом Numbers[Last[i]], то существует и подпоследовательность длины i, заканчивающаяся меньшим элементом, а именно, Numbers[Prev[Last[i]]]. Следовательно, на любом шаге алгоритма последовательность Numbers[Last[0]], Numbers[Last[1]]..., Numbers[Last[i]] возрастает, и мы можем выполнить в ней двоичный поиск очередного элемента за логарифмическое время. На финальной стадии алгоритма наибольшая возрастающая подпоследовательность находится обратным проходом по списку в массиве Prev: ее последний элемент содержится в Numbers[Last[MaxPos]], предпоследний — в Numbers[Prev[Last[MaxPos]]] и т.д.
function LongestIncreasingSubsequence2(const Nums: TNums): TIndex;
var
Prev: TIndex; //Prev[i] - позиция предыдущего числа в цепочке
Last: TIndex; //Last[i] - индекс в массиве Nums последнего числа цепочки длины i+1
MaxPos: integer; //текущая верхняя граница массива Last
i, Left, Right, Cur, NumCount: integer;
begin;
NumCount:=Length(Nums);
if NumCount=0 then SetLength(Result,0)
else begin;
SetLength(Prev, NumCount);
SetLength(Last, NumCount);
MaxPos:=-1;
for i:=0 to NumCount-1 do begin;
Left:=0;
Right:=MaxPos;
while Left<=Right do begin;
Cur:=(Left+Right) shr 1;
if Nums[i]<=Nums[Last[Cur]] then Right:=Cur-1
else Left :=Cur+1;
end;
if Right>=0 then Right:=Last[Right];
Prev[i]:=Right;
Last[Left]:=i;
if MaxPos<Left then MaxPos:=Left;
end;
SetLength(Result, MaxPos+1);
Cur:=Last[MaxPos];
for i:=MaxPos downto 0 do begin;
Result[i]:=Cur;
Cur:=Prev[Cur];
end;
end;
end;Поскольку алгоритм выполняет единственный двоичный поиск для каждого элемента массива, его полное время O(n log n).
Проверить работу алгоритма можно при помощи следующего кода:
procedure TForm1.Button1Click(Sender: TObject);
var
Nums: TNums;
Seq: TIndex;
i: integer;
begin;
SetLength(Nums,10);
Nums[0]:=0;
Nums[1]:=20;
Nums[2]:=10;
Nums[3]:=30;
Nums[4]:=40;
Nums[5]:=80;
Nums[6]:=90;
Nums[7]:=50;
Nums[8]:=60;
Nums[9]:=70;
Seq:=LongestIncreasingSubsequence2(Nums);
Memo1.Lines.Clear;
Memo1.Lines.Add('length: '+IntToStr(Length(Seq)));
for i:=0 to Length(Seq)-1 do Memo1.Lines.Add(Format('%d %d',[Seq[i],Nums[Seq[i]]]));
end;