[BOJ 12738] 가장 긴 증가하는 부분 수열 3

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

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

---

[BOJ 12015] 가장 긴 증가하는 부분 수열 2 과 풀이는 똑같다. 같은 코드로 통과가 된다.

 

---

#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());

}