[백준 c++] 14003 가장 긴 증가하는 부분 수열 5

문제

https://www.acmicpc.net/problem/14003
LIS의 길이와 수열을 출력하는 문제다.

풀이

입력 수열의 크기 N (1 ≤ N ≤ 1,000,000) 따라서 O(N log N)안에 해결해야한다.

LIS 길이는 lower_bound를 이용해서 구했고
수열은 각 위치를 마지막으로 했을 때 LIS길이를 저장하는 배열을 역추적해서 구했다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int n, num[1000001], dp[1000001];
vector<int> v;
stack<int> s;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    for (int i = 0; i < n; i++)
    {
        if (v.empty())
        {
            v.push_back(num[i]);
            dp[i] = 1;
        }
        else
        {
            if (v[v.size() - 1] < num[i])
            {
                v.push_back(num[i]);
                dp[i] = v.size();
            }
            else
            {
                auto p = lower_bound(v.begin(), v.end(), num[i]);
                *(p) = num[i];
                dp[i] = p - v.begin() + 1;
            }
        }
    }
    cout << v.size() << "\n";
    int len = v.size();
    for (int i = n - 1; i >= 0; i--)
    {
        if (dp[i] == len)
        {
            s.push(num[i]);
            len--;
        }
    }
    while (s.size())
    {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}