28 lines
680 B
Plaintext
28 lines
680 B
Plaintext
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>)
|