{"id":825,"date":"2024-10-14T14:28:00","date_gmt":"2024-10-14T08:58:00","guid":{"rendered":"https:\/\/codexplained.in\/?p=825"},"modified":"2025-11-24T15:42:42","modified_gmt":"2025-11-24T10:12:42","slug":"find-highest-increasing-subsequence","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=825","title":{"rendered":"Find Highest Increasing Subsequence"},"content":{"rendered":"\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Increasing Subsequence<\/strong>: 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.<\/li>\n\n\n\n
  2. Dynamic Programming Approach<\/strong>: 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.<\/li>\n<\/ol>\n\n\n\n

    Dynamic Programming Approach<\/h3>\n\n\n\n
      \n
    • Step 1<\/strong>: Initialize an array dp<\/code> where dp[i]<\/code> will hold the length of the longest increasing subsequence that ends with the element at index i<\/code>.<\/li>\n\n\n\n
    • Step 2<\/strong>: For each element, compare it with all previous elements. If the current element is greater than a previous element, update the dp<\/code> value accordingly.<\/li>\n\n\n\n
    • Step 3<\/strong>: The length of the LIS will be the maximum value in the dp<\/code> array.<\/li>\n<\/ul>\n\n\n\n

      C Program to Find Longest Increasing Subsequence<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Function to find the length of Longest Increasing Subsequence\nint longestIncreasingSubsequence(int arr[], int n) {\n    int* dp = (int*)malloc(n * sizeof(int));\n    int maxLength = 0;\n\n    \/\/ Initialize the dp array, each element starts as 1 (itself)\n    for (int i = 0; i < n; i++) {\n        dp[i] = 1; \/\/ Every single element is an increasing subsequence of length 1\n    }\n\n    \/\/ Fill the dp array\n    for (int i = 1; i < n; i++) {\n        for (int j = 0; j < i; j++) {\n            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {\n                dp[i] = dp[j] + 1; \/\/ Update the length if a longer subsequence is found\n            }\n        }\n    }\n\n    \/\/ Find the maximum length from the dp array\n    for (int i = 0; i < n; i++) {\n        if (maxLength < dp[i]) {\n            maxLength = dp[i];\n        }\n    }\n\n    free(dp); \/\/ Free the allocated memory\n    return maxLength;\n}\n\n\/\/ Main function\nint main() {\n    int n;\n\n    \/\/ Input the size of the array\n    printf("Enter the number of elements: ");\n    scanf("%d", &n);\n\n    int* arr = (int*)malloc(n * sizeof(int));\n\n    \/\/ Input the elements of the array\n    printf("Enter the elements: ");\n    for (int i = 0; i < n; i++) {\n        scanf("%d", &arr[i]);\n    }\n\n    \/\/ Find the length of the longest increasing subsequence\n    int lisLength = longestIncreasingSubsequence(arr, n);\n    printf("Length of Longest Increasing Subsequence: %d\\n", lisLength);\n\n    free(arr); \/\/ Free the allocated memory\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Dynamic Programming Table<\/strong>:\n
          \n
        • The program uses a one-dimensional array dp<\/code> where dp[i]<\/code> indicates the length of the LIS that ends at index i<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Filling the DP Array<\/strong>:\n
            \n
          • 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.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Finding the Maximum Length<\/strong>:\n
              \n
            • After populating the dp<\/code> array, the program iterates through it to find the maximum length of any increasing subsequence.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Memory Management<\/strong>:\n
                \n
              • The program dynamically allocates memory for the input array and the dp<\/code> array, and it frees that memory at the end to prevent memory leaks.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output Example<\/h3>\n\n\n\n
                Input<\/h4>\n\n\n\n
                mathematicaCopy codeEnter the number of elements: 8\nEnter the elements: 10 22 9 33 21 50 41 60\n<\/code><\/pre>\n\n\n\n
                Output<\/h4>\n\n\n\n
                mathematicaCopy codeLength of Longest Increasing Subsequence: 5\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                In this case, the longest increasing subsequence is 10, 22, 33, 50, 60<\/code>, which has a length of 5.<\/p>\n\n\n\n
                Conclusion<\/h3>\n\n\n\n
                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.<\/p>\n