Tag Archives: Longest Increasing Subsequence

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_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