Longest Increasing Subsequence (LIS) in C

This document provides a C program to find the longest increasing subsequence in an array. The Longest Increasing Subsequence problem is a classic problem in computer science, and finding an efficient solution is important for various applications.

Program Structure

The provided C program uses a dynamic programming approach to solve the LIS problem. The dynamic programming approach ensures that the solution is computed efficiently by building on previously computed solutions.

Program Code

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

// Function to find the length of the longest increasing subsequence
int longestIncreasingSubsequence(int arr[], int n) {
    int *lis = (int *)malloc(n * sizeof(int));
    int i, j, max = 0;

    // Initialize LIS values for all indices
    for (i = 0; i < n; i++)
        lis[i] = 1;

    // Compute the LIS values in a bottom-up manner
    for (i = 1; i < n; i++) {
        for (j = 0; j < i; j++) {
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }

    // Find the maximum value in lis[]
    for (i = 0; i < n; i++) {
        if (max < lis[i])
            max = lis[i];
    }

    // Free allocated memory
    free(lis);

    return max;
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int length = longestIncreasingSubsequence(arr, n);
    printf("Length of the Longest Increasing Subsequence is %d\n", length);
    return 0;
}

Explanation

• Header Files: The program includes <stdio.h> for input/output functions and <stdlib.h> for memory allocation.
• Function longestIncreasingSubsequence:
  • Input: An integer array arr[] and its size n.
  • Process: The function uses a dynamic array lis[] where lis[i] holds the length of the longest increasing subsequence ending at index i.
  • It initializes lis[i] to 1 for all indices.
  • It then iterates over all pairs of indices to update the lis values based on previous results.
  • The function returns the maximum value found in the lis array, which represents the length of the longest increasing subsequence.
• Main Function:
  • Defines an example array arr[].
  • Calculates the length of the LIS using the longestIncreasingSubsequence function.
  • Prints the length of the LIS.