Longest increasing subsequence: Difference between revisions
m
Added Sidef
m (Added Sidef) |
|||
Line 1,559:
<pre>(2 4 5)
(0 2 6 9 11 15)</pre>
=={{header|Sidef}}==
Dynamic programming:
<lang ruby>func lis(a) {
var l = a.len.of { [] }
l[0] << a[0]
1.to(a.len-1).each { |i|
i.range.each { |j|
if ((a[j] < a[i]) && (l[i].len < l[j].len+1)) {
l[i] = [l[j]...]
}
}
l[i] << a[i]
}
l.max_by { .len }
}
say lis(%i<3 2 6 4 5 1>)
say lis(%i<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>)</lang>
Patience sorting:
<lang ruby>func lis(deck) {
var pileTops = []
deck.each { |x|
var low = 0;
var high = pileTops.end
while (low <= high) {
var mid = ((low + high) // 2)
if (pileTops[mid]{:val} >= x) {
high = mid-1
} else {
low = mid+1
}
}
var i = low
var node = Hash(val => x)
node{:back} = pileTops[i-1] if (i != 0)
pileTops[i] = node
}
var result = []
for (var node = pileTops[-1]; node; node = node{:back}) {
result << node{:val}
}
result.reverse
}
say lis(%i<3 2 6 4 5 1>)
say lis(%i<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>)</lang>
{{out}}
<pre>
[2, 4, 5]
[0, 2, 6, 9, 11, 15]
</pre>
=={{header|Standard ML}}==
| |||