# Longest Increasing Subsequence using dynamic programming in C

A longest increasing subsequence (LIS) of a sequence is a maximal subsequence which is not necessarily contiguous, and is monotonically increasing across its length, and is as long as the longest such subsequence for that sequence. A given sequence may have more than one longest increasing subsequence.

This is a dynamic programming algorithm for finding an LIS of a sequence of integers. It works by building chains of increasing subsequences as it scans the main sequence, and keeping track of a maximum one. At the end of the scan the maximum subsequence chain is read back and copied to an output array.

struct lis_entry {
int value;
int score;
struct lis_entry *prev;
};
typedef struct lis_entry lis_entry;

unsigned int longest_increasing_subsequence(const unsigned int *arr, size_t len,
unsigned int **result)
{
lis_entry *lis;
unsigned int i, j, max = 0;

lis = malloc(len * sizeof(lis_entry));
if (lis == NULL) {
return 0;
}

/* Initialise entries */
for (i = 0; i < len; i++ ) {
lis[i].value = arr[i];
lis[i].score = 1;
lis[i].prev = NULL;
}

/* Calculate LIS scores and build chains */
for (i = 1; i < len; i++ ) {
for (j = 0; j < i; j++ ) {
if (arr[i] > arr[j] && lis[i].score < lis[j].score + 1) {
lis[i].score = lis[j].score + 1;
lis[i].prev = &lis[j];
if (lis[i].score > max) {
max = lis[i].score;
}
}
}
}

/* Allocate the output array and copy the max chain */
*result = malloc(max * sizeof(int));
if (*result != NULL) {
for (i = max - 1; head != NULL; i--) {
}
}
else {
max = 0;
}

free(lis);

return max;
}


An example program using the first few terms of the Van der Corput Sequence:

int main(void)
{
unsigned int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
const size_t len = sizeof(arr)/sizeof(arr);
unsigned int *result;
unsigned int i;
unsigned int lis_length = longest_increasing_subsequence(arr, len, &result);
printf("Length of LIS is %d\n", lis_length);
for (i = 0; i < lis_length; i++) {
printf("%u\n", result[i]);
}
free(result);
return 0;
}


Output:

Length of LIS is 6
0
4
6
9
13
15