Created at : 2025-02-10 21:39
12015

#include <iostream>
#include <vector>

using namespace std;

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

    int N;
    cin >> N;
    vector<int> Numbers(N , 0);
    for(int i = 0; i < N; ++i)
    {
        cin >> Numbers[i];
    }

    vector<int> LIS;
    for(int i = 0; i < Numbers.size(); ++i)
    {
        int j = lower_bound(LIS.begin(), LIS.end(), Numbers[i]) - LIS.begin();
        if(j < LIS.size())
        {
            LIS[j] = Numbers[i];
        }
        else
        {
            LIS.push_back(Numbers[i]);
        }
    }

    cout << LIS.size();

    return 0;
}

유형

이분 탐색
가장 긴 증가하는 부분 수열