Algorithm in A..Z - LIS

개념

LIS(Longest Increasing Subsequence)는 배열이 있을 때 일부 원소를 고른 부분 순열 중, 각 원소가 이전 원소보다 크고 그 순열의 길이가 가장 큰 순열을 LIS라 하고 최장 증가 부분 순열이라고 한다.

 

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

변형 문제로 LDS, 최장 감소 부분 순열이 있다.

---

작동원리

1. LIS라는 List를 만든다.

2. List가 EMPTY거나 제일 마지막 원소가 검사하는 원소보다 작은 경우 List뒤에 추가한다.

3. 검사하는 원소가 List 마지막 원소보다 작은 경우 lower_bound를 사용하여 찾은 index의 값을 검사하는 값으로 대체한다.

4. 원소를 추가할 때 스택의 index와 value를 pair로 저장하고 

5. 검사를 마쳤을 때 List의 크기가 LIS의 길이다. (List의 원소 배열이 LIS의 원소 배열은 아님)

6. 스택에서 pop할 때 가장 처음으로 나오는 index에 value를 추적하여 LIS의 원소 배열을 알 수 있다.

---

시간 복잡도

1. 각 원소를 lower_bound 실행할 때 O(nlogn)

 

O(nlogn)

---

문제

https://www.acmicpc.net/problem/2550

2550번: 전구

---

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    map<int, int> number;
    for (int i = 0;i < n;++i) {
        int index;
        cin >> index;

        number[index] = i;
    }

    vector<int> lis;
    stack<pair<int, int>> st;
    for (int i = 0;i < n;++i) {
        int value;
        cin >> value;

        if (lis.empty() || lis.back() < number[value]) {
            st.push(make_pair(lis.size(), value));
            lis.emplace_back(number[value]);
        } else {
            auto index = distance(lis.begin(), lower_bound(lis.begin(), lis.end(), number[value]));
            st.push(make_pair(index, value));
            lis[index] = number[value];
        }
    }

    cout << lis.size() << "\n";

    int k = (int)lis.size() - 1;
    vector<int> log;
    while (!st.empty() && k >= 0) {
        auto p = st.top(); st.pop();
        if (p.first == k) {
            log.emplace_back(p.second);
            k--;
        }
    }

    sort(log.begin(), log.end());
    for (auto &i : log) {
        cout << i << " ";
    }
}