51 lines
1.3 KiB
D
51 lines
1.3 KiB
D
import std.stdio, std.algorithm, std.range, std.array;
|
|
|
|
T[] lis(T)(in T[] items) pure nothrow
|
|
if (__traits(compiles, T.init < T.init))
|
|
out(result) {
|
|
assert(result.length <= items.length);
|
|
assert(result.isSorted);
|
|
assert(result.all!(x => items.canFind(x)));
|
|
} body {
|
|
if (items.empty)
|
|
return null;
|
|
|
|
static struct Node {
|
|
T value;
|
|
Node* pointer;
|
|
}
|
|
Node*[] pileTops;
|
|
auto nodes = minimallyInitializedArray!(Node[])(items.length);
|
|
|
|
// Sort into piles.
|
|
foreach (idx, x; items) {
|
|
auto node = &nodes[idx];
|
|
node.value = x;
|
|
immutable i = pileTops.length -
|
|
pileTops.assumeSorted!q{a.value < b.value}
|
|
.upperBound(node)
|
|
.length;
|
|
if (i != 0)
|
|
node.pointer = pileTops[i - 1];
|
|
if (i != pileTops.length)
|
|
pileTops[i] = node;
|
|
else
|
|
pileTops ~= node;
|
|
}
|
|
|
|
// Extract LIS from nodes.
|
|
size_t count = 0;
|
|
for (auto n = pileTops[$ - 1]; n != null; n = n.pointer)
|
|
count++;
|
|
auto result = minimallyInitializedArray!(T[])(count);
|
|
for (auto n = pileTops[$ - 1]; n != null; n = n.pointer)
|
|
result[--count] = n.value;
|
|
return result;
|
|
}
|
|
|
|
void main() {
|
|
foreach (d; [[3,2,6,4,5,1],
|
|
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])
|
|
d.writeln;
|
|
}
|