Longest increasing subsequence: Difference between revisions
Added 11l
m (added ;Related tasks.) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 14:
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]].
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F longest_increasing_subsequence(x)
V n = x.len
V P = [0] * n
V M = [0] * (n + 1)
V l = 0
L(i) 0 .< n
V lo = 1
V hi = l
L lo <= hi
V mid = (lo + hi) I/ 2
I (x[M[mid]] < x[i])
lo = mid + 1
E
hi = mid - 1
V newl = lo
P[i] = M[newl - 1]
M[newl] = i
I (newl > l)
l = newl
[Int] s
V k = M[l]
L(i) (l - 1 .. 0).step(-1)
s.append(x[k])
k = P[k]
R reversed(s)
L(d) [[3, 2, 6, 4, 5, 1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]
print(‘a L.I.S. of #. is #.’.format(d, longest_increasing_subsequence(d)))</lang>
{{out}}
<pre>
a L.I.S. of [3, 2, 6, 4, 5, 1] is [2, 4, 5]
a L.I.S. of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] is [0, 2, 6, 9, 11, 15]
</pre>
=={{header|360 Assembly}}==
| |||