Longest increasing subsequence: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→Dynamic programming: 'strict' compliant) |
No edit summary |
||
Line 1,262: | Line 1,262: | ||
0 2 6 9 11 15 |
0 2 6 9 11 15 |
||
</pre> |
</pre> |
||
=={{header|M2000 Interpreter}}== |
|||
stack:=stackitem(L(i)), ! stack(L(j)) returns a refence to a new stack object, with the first item on L(i) (which is a reference to stack object) and merge using ! the copy of L(j) stack. |
|||
<lang M2000 Interpreter> |
|||
Module LIS_example { |
|||
Function LIS { |
|||
LD=Stack.Size-1 |
|||
dim L(0 to LD) |
|||
For i=0 to LD : Read V: L(i):=Stack:=V:next |
|||
M=1 |
|||
M1=LD |
|||
for i=LD-1 to 0 |
|||
for j=LD to i+1 |
|||
if stackitem(L(i))<stackitem(L(j)) then |
|||
if len(L(i))<=len(L(j)) then L(i) =stack:=stackitem(L(i)), ! stack(L(j)) |
|||
end if |
|||
next |
|||
if len(L(i))>=M then M1=i:M=Len(L(i)) |
|||
next |
|||
=L(M1) |
|||
} |
|||
Const seq$="sequence", subseq$="Longest increasing subsequence" |
|||
Document doc$ |
|||
Disp(seq$, Stack:=3,2,6,4,5,1) |
|||
Disp(subseq$, Lis(3,2,6,4,5,1)) |
|||
Disp(seq$, Stack:=0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15) |
|||
Disp(subseq$, LIS(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)) |
|||
Print #-2,Doc$ |
|||
Clipboard Doc$ |
|||
Sub Disp(title$, m) |
|||
local n=each(m), s$ |
|||
while n |
|||
s$+=", "+str$(stackitem(n),"") |
|||
end while |
|||
s$=trim$(mid$(s$, 2)) |
|||
Doc$=title$+": "+s$+{ |
|||
} |
|||
End Sub |
|||
} |
|||
LIS_example |
|||
</lang> |
|||
{{out}} |
|||
<pre style="height:30ex;overflow:scroll"> |
|||
sequence: 3, 2, 6, 4, 5, 1 |
|||
Longest increasing subsequence: 3, 4, 5 |
|||
sequence: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 |
|||
Longest increasing subsequence: 0, 2, 6, 9, 11, 15 |
|||
</pre > |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |