27 lines
582 B
Plaintext
27 lines
582 B
Plaintext
# dynamic programming:
|
|
LIS := proc(L)
|
|
local i, j;
|
|
local index := 1;
|
|
local output := Array(1..numelems(L), i -> Array(1..0));
|
|
|
|
for i from 1 to numelems(L) do
|
|
for j from 1 to i - 1 do
|
|
if (L[j] < L[i]) and (upperbound(output[j]) > upperbound(output[i])) then
|
|
output[i] := copy(output[j]);
|
|
end if;
|
|
end do;
|
|
# append current value
|
|
output[i] ,= L[i];
|
|
end do;
|
|
|
|
#output longest subsequence using loop
|
|
for i from 2 to numelems(L) do
|
|
if (upperbound(output[i]) > upperbound(output[index])) then
|
|
index := i;
|
|
end if;
|
|
end do;
|
|
|
|
return output[index];
|
|
|
|
end proc:
|