14003 가장 긴 증가하는 부분 수열 5

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

14003번: 가장 긴 증가하는 부분 수열 5

 

수열의 최대 크기가 1,000,000 인 LIS 문제이다.

LIS 의 크기만 구하는 문제가 아닌, 정답이 될 수 있는 LIS 하나 출력하는 문제.

 

\( O(NlogN) \) LIS 알고리즘 (이분탐색) + 넣을 때마다 인덱싱 저장으로 문제를 해결할 수 있었음.

 

/*

수정 중

*/

 

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int _lower_bound(int start, int end, int key, vector<int>& v)
{
    while(start < end)
    {
        int mid = (start+end)/2;
        if(key > v[mid]) start = mid+1;
        else end = mid;
    }
    return end+1;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n; 
    cin >> n;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++)
        cin >> v[i];
 
    vector<int> lis(n, 0), pos(n, 0);
    int lisp = 0;
    lis[lisp] = v[0];
    pos[0] = 0;
    for(int i=1;i<n;i++)
    {
        if(lis[lisp] < v[i])
        {
            lis[++lisp] = v[i];
            pos[i] = lisp;
        }
        else
        {
            int k = _lower_bound(0, lisp, v[i], lis);
            lis[k-1] = v[i];
            pos[i] = k-1;    
        }
    }
    cout << lisp+1 << endl;
    int k = lisp;
    vector<int> ans;
    for(int i=n-1;i>=0;i--)
    {
        if(pos[i] == k)
        {
            ans.push_back(v[i]);
            k--;
        }
    }
    reverse(ans.begin(), ans.end());
    for(auto &K : ans)
        cout << K << ' ';
    cout << endl;
 
 
    return 0;
}