{"id":34122,"date":"2024-11-01T09:24:24","date_gmt":"2024-11-01T09:24:24","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34122"},"modified":"2024-11-01T10:58:31","modified_gmt":"2024-11-01T10:58:31","slug":"c-coding-test-course-finding-the-longest-increasing-subsequence-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34122\/","title":{"rendered":"C++ Coding Test Course, Finding the Longest Increasing Subsequence"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n You need to find the Longest Increasing Subsequence (LIS) in a given integer array.
\n A subsequence is made up of selected elements while maintaining the order of elements from the original array.
\n This problem can be solved using Dynamic Programming or Binary Search.\n <\/p>\n

Example<\/h2>\n

\nInput:<\/strong> [10, 9, 2, 5, 3, 7, 101, 18]<\/code>
\nOutput:<\/strong> 4<\/code> (Longest Increasing Subsequence: [2, 3, 7, 101])\n <\/p>\n

Approach to the Problem<\/h2>\n

\n There are several ways to solve this problem. The most representative method is using dynamic programming,
\n which has a time complexity of O(N^2). However, this problem can also be solved using binary search with a time complexity of O(N log N).\n <\/p>\n

1. Dynamic Programming Approach<\/h3>\n

\n The key to the dynamic programming approach is to store ‘intermediate results’ to avoid repeating the same calculations.
\n It proceeds in the following steps.\n <\/p>\n

    \n
  1. Initialize a dp array to store the lengths. dp[i] stores the maximum length of the increasing subsequence ending with the element at index i.<\/li>\n
  2. Use a nested loop to compare each element and update the dp array.
    \n If the i-th element is greater than the j-th element, set dp[i] to max(dp[i], dp[j] + 1).<\/li>\n
  3. Finally, find the maximum value in the dp array and output it.<\/li>\n<\/ol>\n

    Code (Dynamic Programming)<\/h3>\n
    \n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nint lengthOfLIS(vector& nums) {\n    if (nums.empty()) return 0;\n    vector dp(nums.size(), 1);\n    \n    for (int i = 1; i < nums.size(); i++) {\n        for (int j = 0; j < i; j++) {\n            if (nums[i] > nums[j]) {\n                dp[i] = max(dp[i], dp[j] + 1);\n            }\n        }\n    }\n    return *max_element(dp.begin(), dp.end());\n}\n\nint main() {\n    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};\n    cout << \"Length of the longest increasing subsequence: \" << lengthOfLIS(nums) << endl;\n    return 0;\n}\n    <\/int><\/int><\/int><\/code><\/pre>\n
    2. Binary Search Approach<\/h3>\n
    \n        This method is more efficient, having a time complexity of O(N log N). The basic idea of this method is
    \n        to maintain an array that contains ‘the last elements of the subsequences’.\n    <\/p>\n
      \n
    1. Initialize an array to store the results.<\/li>\n
    2. For each element, perform the following:\n