Find Highest Increasing Subsequence

Key Concepts

1. Increasing Subsequence: A subsequence is a sequence derived from another sequence where some elements are deleted, but the order of the remaining elements is preserved. An increasing subsequence has all its elements in ascending order.
2. Dynamic Programming Approach: The problem can be solved using a dynamic programming method where we maintain an array to store the lengths of the longest increasing subsequences found so far.

Dynamic Programming Approach

• Step 1: Initialize an array dp where dp[i] will hold the length of the longest increasing subsequence that ends with the element at index i.
• Step 2: For each element, compare it with all previous elements. If the current element is greater than a previous element, update the dp value accordingly.
• Step 3: The length of the LIS will be the maximum value in the dp array.

C Program to Find Longest Increasing Subsequence

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

// Function to find the length of Longest Increasing Subsequence
int longestIncreasingSubsequence(int arr[], int n) {
    int* dp = (int*)malloc(n * sizeof(int));
    int maxLength = 0;

    // Initialize the dp array, each element starts as 1 (itself)
    for (int i = 0; i < n; i++) {
        dp[i] = 1; // Every single element is an increasing subsequence of length 1
    }

    // Fill the dp array
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1; // Update the length if a longer subsequence is found
            }
        }
    }

    // Find the maximum length from the dp array
    for (int i = 0; i < n; i++) {
        if (maxLength < dp[i]) {
            maxLength = dp[i];
        }
    }

    free(dp); // Free the allocated memory
    return maxLength;
}

// Main function
int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));

    // Input the elements of the array
    printf("Enter the elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Find the length of the longest increasing subsequence
    int lisLength = longestIncreasingSubsequence(arr, n);
    printf("Length of Longest Increasing Subsequence: %d\n", lisLength);

    free(arr); // Free the allocated memory
    return 0;
}

Explanation of the Code

1. Dynamic Programming Table:
   • The program uses a one-dimensional array dp where dp[i] indicates the length of the LIS that ends at index i.
2. Filling the DP Array:
   • The nested loops compare each element with the previous ones. If the current element is greater than a previous one, the LIS length is updated.
3. Finding the Maximum Length:
   • After populating the dp array, the program iterates through it to find the maximum length of any increasing subsequence.
4. Memory Management:
   • The program dynamically allocates memory for the input array and the dp array, and it frees that memory at the end to prevent memory leaks.

Input and Output Example

Input

mathematicaCopy codeEnter the number of elements: 8
Enter the elements: 10 22 9 33 21 50 41 60

Output

mathematicaCopy codeLength of Longest Increasing Subsequence: 5

Explanation of the Output

In this case, the longest increasing subsequence is 10, 22, 33, 50, 60, which has a length of 5.

Conclusion

This C program efficiently finds the Longest Increasing Subsequence using dynamic programming. It allows user input for flexibility and displays the length of the LIS. You can test various sequences to see how the LIS changes. This approach is optimal for practical applications, including stock price analysis and data compression.