[백준/BOJ] 백준 12738번 : 가장 긴 증가하는 부분 수열 3

www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다

 

코드

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

int n;
vector<int> A;
vector<int> make_long;
vector<int>::iterator it;

//가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		A.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		it = lower_bound(make_long.begin(), make_long.end(), A[i]);

		if (it == make_long.end())
			make_long.push_back(A[i]);

		else
			*it = A[i];
	}

	cout << make_long.size();

	return 0;
}