[알고리즘] c++ cpp 가장 긴 증가하는 부분 수열 2

포인트

1. 이분 탐색을 사용하여 시간 복잡도 O(nlogn) 으로 만들어준다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

int main() {
	int n, temp, cnt = 0;
	vector<int> vc;

	// vc.push_back(-987654321); //음수 값을 넣어준다.

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		if(vc.empty()) {
			vc.push_back (temp);
			cnt+=1;
			continue;
		}
		if (temp > vc.back()) {
			vc.push_back(temp);
			cnt+=1;
		}
		else {
			auto it = lower_bound(vc.begin(), vc.end(), temp); //이분 탐색 중 하나로 없으면 temp 다음 큰 값중 가장 작은 값으로 가르킨다
			*it = temp;
		}
	}

	cout << vc.size () << '\n';

	return 0;
}