Question

How to find the longest increasing subsequence (LIS) of a sequence of numbers in C

Answer 1

#include <stdio.h>
#include <stdlib.h>

int longestIncreasingSubsequence(int* nums, int size) {
    if (size == 0) return 0;

    int* length = (int*)malloc(size * sizeof(int));
    if (length == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        return -1;
    }

    for (int i = 0; i < size; i++) {
        length[i] = 1;
    }

    int maxLength = 1;

    for (int i = 1; i < size; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && length[i] < length[j] + 1) {
                length[i] = length[j] + 1;
            }
        }
        if (length[i] > maxLength) {
            maxLength = length[i];
        }
    }

    free(length);
    
    return maxLength;
}

int main() {
    int nums[] = {4, 5, 1, 10, 3, 9, 18, 19};
    int size = sizeof(nums) / sizeof(nums[0]);

    int result = longestIncreasingSubsequence(nums, size);
    printf("Length of LIS: %d\n", result);

    return 0;
}

 
 
/*
run:
   
Length of LIS: 5
 
*/

 

70+ SQL courses for beginners and professionals