LIS(Longest Increasing Subsequence)

arr = [ 1, 4, 2, 3, 6 ] 이런 수열에서 어떻게 하면 LIS를 찾을 수 있을까?

Naive 1

0부터 순서대로 조사하여, 매번 arr[i]를 포함하거나, 포함하지 않는 경로를 비교함으로써 모든 경로를 조사할 수 있다.
시간복잡도는 O(2^N)이 된다.

Better 1

이번에는 끝나는 지점 i를 미리 정해서, 그 지점에서의 최대를 구하고자 해보자.
LIS(i) = LIS(0)..LIS(i-1) 중에서 arr[i]로 끝낼 수 있는 최대를 선택하면 된다.
시간 복잡도는 O(N^2), 공간 복잡도는 O(N^2)이 된다.

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

// Function to construct and print Longest 
// Increasing Subsequence
vector<int> getLIS(vector<int>& arr){
    
    // L[i] - The longest increasing 
    // sub-sequence ends with arr[i]
    int n = arr.size();
    vector<vector<int>> L(n);

    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);

    // Start from index 1
    for (int i = 1; i < n; i++){
        
        int lis = 1;

        // Do for every prev less than i
        for (int prev = 0; prev < i; prev++){
            
            /* L[i] = {Max(L[prev])} + arr[i]
               where prev < i and arr[prev] < arr[i] */
            if ((arr[i] > arr[prev]) && 
                (lis < L[prev].size() + 1)) {
              
                // Copy the vector of prev and update lis of i
                L[i] = L[prev];
                lis = L[prev].size() + 1;
            }
        }

        // L[i] ends with arr[i]
        L[i].push_back(arr[i]);
    }

    // L[i] now stores increasing sub-sequence 
    // of arr[0..i] that ends with arr[i]
    vector<int> res = L[0];

    // LIS will be max of all increasing 
    // sub-sequences of arr
    for (vector<int> x : L)
        if (x.size() > res.size())
            res = x;
    return res;
}

// Driver function
int main(){

    vector<int> arr = {10, 20, 3, 40};
    
    vector<int> max_lis = getLIS(arr);
    for (int x : max_lis)
        cout << x << " ";
    return 0;
}

Better 2

Better 1의 경우 N이 10,000개 정도 들어와도 시간상 1초 내로 해결은 가능하지만, 공간은 100MB를 차지하게 된다.
공간복잡도를 줄일 순 없을까?

매 LIS마다 순열을 저장하기 보다는, LIS(i)를 만들기 위해 어떤 LIS(j) (j<=i)와 연결되었는지 표시하면 매 LIS마다 순열을 저장할 필요가 없을 것이다.

시간 복잡도는 O(N^2)으로 동일하고, 공간복작도는 O(N)으로 개선되었다.

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

// Function to find the longest increasing 
// subsequence.
vector<int> getLIS(vector<int>& arr) {
   
    int n = arr.size();
  
    // Initialize dp array with 1.
    vector<int> dp(n, 1);
  
    // Initialize hash array with index values.
    // We store previous indexs in LIS here
    vector<int> seq(n);

    for (int i = 0; i < n; i++) {
      
        seq[i] = i; // Mark element itself as prev
      
        for (int prev = 0; prev < i; prev++) {
          
            // Update dp and hash values if 
            // condition satisfies.
            if (arr[prev] < arr[i] && 
                1 + dp[prev] > dp[i]) {
              
                dp[i] = 1 + dp[prev];
                seq[i] = prev;
            }
        }
    }

    // Now we find the last element 
    // in LIS using dp[]
    int ans = -1;
    int ansInd = -1;
    for (int i = 0; i < n; i++) {
        if (dp[i] > ans) {
            ans = dp[i];
            ansInd = i;
        }
    }

    // Now construct result sequence using seq[]
    // and ans_ind
    vector<int> res;
    res.push_back(arr[ansInd]);
    while (seq[ansInd] != ansInd) {
        ansInd = seq[ansInd];
        res.push_back(arr[ansInd]);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    vector<int> arr = {10, 20, 3, 40};

    vector<int> max_lis = getLIS(arr);

    for (int num : max_lis) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Solution

Binary Search를 사용하는 방법이다.
시간 복잡도는 O(NlogN), 공간복잡도는 O(N)이 된다.

// Binary Search Approach of Finding LIS by
// reducing the problem to longest
// common Subsequence
#include <bits/stdc++.h>
using namespace std;

int lengthOfLIS(vector<int>& arr)
{

    // Binary search approach
    int n = arr.size();
    vector<int> ans;

    // Initialize the answer vector with the
    // first element of arr
    ans.push_back(arr[0]);

    for (int i = 1; i < n; i++) {
        if (arr[i] > ans.back()) {

            // If the current number is greater
            // than the last element of the answer
            // vector, it means we have found a
            // longer increasing subsequence.
            // Hence, we append the current number
            // to the answer vector.
            ans.push_back(arr[i]);
        }
        else {

            // If the current number is not
            // greater than the last element of
            // the answer vector, we perform
            // a binary search to find the smallest
            // element in the answer vector that
            // is greater than or equal to the
            // current number.

            // The lower_bound function returns
            // an iterator pointing to the first
            // element that is not less than
            // the current number.
            int low = lower_bound(ans.begin(), ans.end(),
                                  arr[i])
                      - ans.begin();

            // We update the element at the
            // found position with the current number.
            // By doing this, we are maintaining
            // a sorted order in the answer vector.
            ans[low] = arr[i];
        }
    }

    // The length of the answer vector
    // represents the length of the
    // longest increasing subsequence.
    return ans.size();
}

// Driver program to test above function
int main()
{
    vector<int> arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
    printf("Length of LIS is %d\n", lengthOfLIS(arr));
    return 0;
}

cf

• LIS까지 출력

Reference

• https://www.geeksforgeeks.org/dsa/longest-monotonically-increasing-subsequence-size-n-log-n/
• https://www.geeksforgeeks.org/dsa/longest-increasing-subsequence-dp-3/#using-binary-search-on-log-n-time-and-on-space
• https://www.geeksforgeeks.org/dsa/construction-of-longest-increasing-subsequence-using-dynamic-programming/