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_entry *head; 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; head = &lis[i]; } } } } /* Allocate the output array and copy the max chain */ *result = malloc(max * sizeof(int)); if (*result != NULL) { for (i = max - 1; head != NULL; i--) { (*(result))[i] = head->value; head = head->prev; } } 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[0]); 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