Longest increasing subsequence: Difference between revisions
added Pascal example
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(added Pascal example) |
||
Line 1,980:
# lis compare [0; 8; 4; 12; 2; 10; 6; 14; 1; 9; 5; 13; 3; 11; 7; 15];;
- : int list = [0; 2; 6; 9; 11; 15]</pre>
=={{header|Pascal}}==
{{works with|FPC}}
O(NLogN) version.
<syntaxhighlight lang="pascal">
program LisDemo;
{$mode objfpc}{$h+}
uses
SysUtils;
function Lis(const A: array of Integer): specialize TArray<Integer>;
var
TailIndex: array of Integer;
function CeilIndex(Value, R: Integer): Integer;
var
L, M: Integer;
begin
L := 0;
while L < R do begin
{$PUSH}{$Q-}{$R-}M := (L + R) shr 1;{$POP}
if A[TailIndex[M]] < Value then L := M + 1
else R := M;
end;
Result := R;
end;
var
I, J, Len: Integer;
Parents: array of Integer;
begin
Result := nil;
if Length(A) = 0 then exit;
SetLength(TailIndex, Length(A));
SetLength(Parents, Length(A));
Len := 1;
for I := 1 to High(A) do
if A[I] < A[TailIndex[0]] then
TailIndex[0] := I
else
if A[TailIndex[Len-1]] < A[I] then begin
Parents[I] := TailIndex[Len - 1];
TailIndex[Len] := I;
Inc(Len);
end else begin
J := CeilIndex(A[I], Len - 1);
Parents[I] := TailIndex[J - 1];
TailIndex[J] := I;
end;
if Len < 2 then exit([A[0]]);
SetLength(Result, Len);
J := TailIndex[Len - 1];
for I := Len - 1 downto 0 do begin
Result[I] := A[J];
J := Parents[J];
end;
end;
procedure PrintArray(const A: array of Integer);
var
I: SizeInt;
begin
Write('[');
for I := 0 to High(A) - 1 do
Write(A[I], ', ');
WriteLn(A[High(A)], ']');
end;
begin
PrintArray(Lis([3, 2, 6, 4, 5, 1]));
PrintArray(Lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
PrintArray(Lis([1, 1, 1, 1, 1, 0]));
end.
</syntaxhighlight>
{{out}}
<pre>
[2, 4, 5]
[0, 2, 6, 9, 11, 15]
[1]
</pre>
=={{header|Perl}}==
| |||