Longest increasing subsequence: Difference between revisions
→{{header|Phix}}
PatGarrett (talk | contribs) m (→{{header|360 Assembly}}: Superfluous blanks suppressed) |
|||
Line 1,451:
<pre>[2 4 5]
[0 2 6 9 11 15]</pre>
=={{header|Phix}}==
Using the Wikipedia algorithm (converted to 1-based indexing)
<lang Phix>function lis(sequence X, integer N = length(X))
sequence P = repeat(0,N)
sequence M = repeat(0,N)
integer len = 0
for i=1 to N do
integer lo = 1
integer hi = len
while lo<=hi do
integer mid = ceil((lo+hi)/2)
if X[M[mid]]<X[i] then
lo = mid + 1
else
hi = mid - 1
end if
end while
if lo>1 then
P[i] = M[lo-1]
end if
M[lo] = i
if lo>len then len = lo end if
end for
sequence res = repeat(0,len)
if len>0 then
integer k = M[len]
for i=len to 1 by -1 do
res[i] = X[k]
k = P[k]
end for
end if
return res
end function
constant tests = {{3, 2, 6, 4, 5, 1},
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}}
for i=1 to length(tests) do
?lis(tests[i])
end for</lang>
{{out}}
<pre>
{2,4,5}
{0,2,6,9,11,15}
</pre>
=={{header|PHP}}==
| |||