Longest increasing subsequence: Difference between revisions
Content added Content deleted
(Fixed a bug with empty input, removed useless index, and better formatting for second Python entry) |
(+ D entry) |
||
Line 10: | Line 10: | ||
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube |
# [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]]. |
# 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}}== |
=={{header|Déjà Vu}}== |