Longest increasing subsequence: Difference between revisions
Added Wren
Alextretyak (talk | contribs) (Added 11l) |
(Added Wren) |
||
Line 2,581:
2,4,5,
0,2,6,9,11,15,
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<lang ecmascript>var longestIncreasingSubsequence = Fn.new { |x|
var n = x.count
if (n == 0) return []
if (n == 1) return x
var p = List.filled(n, 0)
var m = List.filled(n+1, 0)
var len = 0
for (i in 0...n) {
var lo = 1
var hi = len
while (lo <= hi) {
var mid = ((lo + hi)/2).ceil
if (x[m[mid]] < x[i]) {
lo = mid + 1
} else {
hi = mid - 1
}
}
var newLen = lo
p[i] = m[newLen - 1]
m[newLen] = i
if (newLen > len) len = newLen
}
var s = List.filled(len, 0)
var k = m[len]
for (i in len-1..0) {
s[i] = x[k]
k = p[k]
}
return s
}
var lists = [
[3, 2, 6, 4, 5, 1],
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
]
lists.each { |l| System.print(longestIncreasingSubsequence.call(l)) }</lang>
{{out}}
<pre>
[2, 4, 5]
[0, 2, 6, 9, 11, 15]
</pre>
| |||