Anonymous user
Longest increasing subsequence: Difference between revisions
+ D entry
(Fixed a bug with empty input, removed useless index, and better formatting for second Python entry) |
(+ D entry) |
||
Line 10:
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]].
=={{header|D}}==
{{trans|Python}}
From the second Python entry, using the Patience sorting method.
<lang d>import std.stdio, std.algorithm, std.array;
/// Return one of the Longest Increasing Subsequence of
// items using patience sorting.
T[] lis(T)(T[] items) if (__traits(compiles, T.init < T.init)) {
if (items.empty)
return null;
static struct Node { T val; Node* back; }
auto pile = [[new Node(items[0], null)]];
OUTER: foreach (di; items[1 .. $]) {
foreach (immutable j, ref pj; pile)
if (pj[$ - 1].val > di) {
pj ~= new Node(di, j ? pile[j - 1][$ - 1] : null);
continue OUTER;
}
pile ~= [new Node(di, pile[$ - 1][$ - 1])];
}
T[] result;
for (auto ptr = pile[$ - 1][$ - 1]; ptr != null; ptr = ptr.back)
result ~= ptr.val;
result.reverse();
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.lis.writeln;
}</lang>
<pre>[2, 4, 5]
[0, 2, 6, 9, 11, 15]</pre>
=={{header|Déjà Vu}}==
| |||