Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Longest increasing subsequence (LIS)

LIS is the longest strictly increasing subsequence that preserves input order without requiring adjacent elements. The C example computes its length using dynamic programming in O(n²) time with O(n) auxiliary space.

Version: C23; repository compiler flag, production runtime not attested

Syntax

dp[i] = max({1} union {dp[j] + 1 | 0 <= j < i and a[j] < a[i]}); LIS length = n == 0 ? 0 : max(dp)

A longest increasing subsequence (LIS) selects elements in their original order. Elements may be skipped; the selection need not be contiguous. For {3, 1, 2, 2, 4}, the subsequence {1, 2, 4} has the maximum length 3. Sorting the input would change the problem by losing the original order.

The distinction strictly increasing versus non-decreasing means that a strictly increasing subsequence requires <, whereas a non-decreasing one allows <=. Equal values do not extend an LIS. Replacing a[j] < a[i] with a[j] <= a[i] produces an algorithm for the longest non-decreasing subsequence; its length for the example input is 4.

Let dp[i] be the best subsequence length ending exactly at a[i]. Initialize it to 1. For each j < i satisfying a[j] < a[i], consider dp[j] + 1. Compute states from left to right and retain the largest result. The nested loops take O(n²) time, and the dp array uses O(n) auxiliary space.

The example returns only the length. Recording predecessor indices is optional: for nonempty input, you can reconstruct an LIS from a and dp. Start by selecting a[i] at an index i where dp[i] is maximal. Scan backward, selecting a[j] whenever j < i, a[j] < a[i], and dp[j] + 1 == dp[i], and updating i to j after each selection. Stop when dp[i] == 1 and reverse the selected elements.

The caller provides non-overlapping arrays a and dp, each holding at least n elements. For n == 0, the function returns 0 without accessing either array, so NULL is allowed. It uses neither dynamic allocation nor variable-length arrays.

Examples

#include <stddef.h>
#include <stdio.h>

/* For n > 0, a and dp must each provide at least n elements.
   Their storage must not overlap. For n == 0, both may be NULL. */
static size_t lis_length(const int *a, size_t n, size_t *dp)
{
    size_t best = 0;
    for (size_t i = 0; i < n; ++i) {
        dp[i] = 1;
        for (size_t j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > best) {
            best = dp[i];
        }
    }
    return best;
}

int main(void)
{
    const int a[] = {3, 1, 2, 2, 4};
    size_t dp[sizeof a / sizeof a[0]];
    printf("LIS length: %zu\n", lis_length(a, sizeof a / sizeof a[0], dp));
    printf("Empty length: %zu\n", lis_length(NULL, 0, NULL));
    return 0;
}

Result

LIS length: 3
Empty length: 0

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources