Anonymous user
Longest increasing subsequence: Difference between revisions
→{{header|C}}: +C
(Add Racket Implementation) |
(→{{header|C}}: +C) |
||
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|C}}==
Using an array that doubles as linked list (more like reversed trees really). O(n) memory and O(n<sup>2</sup>) runtime.
<lang c>#include <stdio.h>
#include <stdlib.h>
struct node {
int val, len;
struct node *next;
};
void lis(int *v, int len)
{
int i;
struct node *p, *n = calloc(len, sizeof *n);
for (i = 0; i < len; i++)
n[i].val = v[i];
for (i = len; i--; ) {
// find longest chain that can follow n[i]
for (p = n + i; p++ < n + len; ) {
if (p->val > n[i].val && p->len >= n[i].len) {
n[i].next = p;
n[i].len = p->len + 1;
}
}
}
// find longest chain
for (i = 0, p = n; i < len; i++)
if (n[i].len > p->len) p = n + i;
do printf(" %d", p->val); while ((p = p->next));
putchar('\n');
free(n);
}
int main(void)
{
int x[] = { 3, 2, 6, 4, 5, 1 };
int y[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
lis(x, sizeof(x) / sizeof(int));
lis(y, sizeof(y) / sizeof(int));
return 0;
}</lang>
{{out}}
<pre>
3 4 5
0 4 6 9 13 15
</pre>
=={{header|C++}}==
| |||