[BOJ 12015] 가장 긴 증가하는 부분 수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

---

해당 문제 [BOJ 11053] 가장 긴 증가하는 부분 수열 문제와 거의 똑같다.

 

다만 배열의 크기가 1,000,000이기 때문에 위에서 쓴 O(N^2) 알고리즘으로는 못 푼다.

 

대신 O(N log N) 알고리즘을 이용하여 풀면 된다.

 

자세한 풀이는 LIS 에 있다.

---

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;

int main()
{
	scanf("%d", &n);

	vector<int> dp;
	for (int i = 1; i <= n; i++)
	{
		int t;
		scanf("%d",&t);
		if (dp.size() == 0 || t > dp.back()) dp.push_back(t);
		else
		{
			vector<int>::iterator it = lower_bound(dp.begin(), dp.end(), t);
			*it = t;
		}
	}

	printf("%lu", dp.size());

}