백준 LIS 2 - 12015

배열 크기가 더 커진 LIS 풀이에는 차이가 없다. 중요한건 lower_boung 를 사용해서 lis 의 크기를 유지하면서도 lis 내용을 갱신해준다.

 

#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;
}