C++ Coding Test Course, Finding the Longest Increasing Subsequence

Problem Description

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

Example

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4 (Longest Increasing Subsequence: [2, 3, 7, 101])

Approach to the Problem

There are several ways to solve this problem. The most representative method is using dynamic programming,
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).

1. Dynamic Programming Approach

The key to the dynamic programming approach is to store ‘intermediate results’ to avoid repeating the same calculations.
It proceeds in the following steps.

  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.
  2. Use a nested loop to compare each element and update the dp array.
    If the i-th element is greater than the j-th element, set dp[i] to max(dp[i], dp[j] + 1).
  3. Finally, find the maximum value in the dp array and output it.

Code (Dynamic Programming)


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    if (nums.empty()) return 0;
    vector dp(nums.size(), 1);
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of the longest increasing subsequence: " << lengthOfLIS(nums) << endl;
    return 0;
}

2. Binary Search Approach

This method is more efficient, having a time complexity of O(N log N). The basic idea of this method is
to maintain an array that contains ‘the last elements of the subsequences’.

  1. Initialize an array to store the results.
  2. For each element, perform the following:
    • If the current number is greater than the last element of the result array, add it to the array.
    • Otherwise, use binary search to find the position where the current number should go and replace it.
  3. The size of the result array will be the length of the longest increasing subsequence.

Code (Binary Search)


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    vector tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of the longest increasing subsequence: " << lengthOfLIS(nums) << endl;
    return 0;
}

Conclusion

The problem of “Finding the Longest Increasing Subsequence” is an algorithm problem that can be solved in various ways.
Understanding and implementing approaches to solve problems is very helpful in coding tests.
Through this problem, learn the basics of dynamic programming and binary search, and develop the ability to apply them to various algorithm problems.

Additional Learning Resources