52 lines
1.4 KiB
Ada
52 lines
1.4 KiB
Ada
with Ada.Text_IO;
|
|
|
|
procedure Longest_Increasing_Subsequence is
|
|
type Sequence is array (Positive range <>) of Integer;
|
|
|
|
Seq1 : constant Sequence :=
|
|
(3, 2, 6, 4, 5, 1);
|
|
Seq2 : constant Sequence :=
|
|
(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15);
|
|
|
|
function Lis (Seq : Sequence) return Sequence is
|
|
Best : Sequence (Seq'Range) := (others => 1);
|
|
Pred : Sequence (Seq'Range) := (others => 0);
|
|
Best_Idx, Max_Len : Natural := 0;
|
|
begin
|
|
-- Calculate LIS length for every end point
|
|
for I in Seq'Range loop
|
|
for J in 1 .. I - 1 loop
|
|
if Seq (J) < Seq (I) and then
|
|
Best (I) < 1 + Best (J) then
|
|
Best (I) := 1 + Best (J);
|
|
Pred (I) := J;
|
|
end if;
|
|
end loop;
|
|
end loop;
|
|
|
|
-- Find tail of global LIS
|
|
for I in Best'Range loop
|
|
if Best (I) > Max_Len then
|
|
Best_Idx := I;
|
|
Max_Len := Best (I);
|
|
end if;
|
|
end loop;
|
|
|
|
-- Trace sequence
|
|
declare
|
|
Lis : Sequence (1 .. Max_Len);
|
|
begin
|
|
for I in reverse 1 .. Max_Len loop
|
|
Lis (I) := Seq (Best_Idx);
|
|
Best_Idx := Pred (Best_Idx);
|
|
end loop;
|
|
|
|
return Lis;
|
|
end;
|
|
end Lis;
|
|
|
|
begin
|
|
Ada.Text_IO.Put_Line (Lis (Seq1)'Image);
|
|
Ada.Text_IO.Put_Line (Lis (Seq2)'Image);
|
|
end Longest_Increasing_Subsequence;
|