백준 11053 LIS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;


int main(void)
{
	int n;
	cin >> n;

	vector<int> arr(n);

	for (int i = 0; i < arr.size(); ++i)
	{
		cin >>arr[i];
	}

	vector<int> lis;
	lis.push_back(arr[0]);

	for (int i = 1; i < n; ++i)
	{
		if (arr[i] > lis.back())
		{
			lis.push_back(arr[i]);
		}
		else
		{
			auto iter = lower_bound(lis.begin(), lis.end(), arr[i]);
			*iter = arr[i];
		}
	}
	cout << lis.size();
	return 0;
}