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

포인트

1.가장 긴 증가하는 부분 수열 2하고 똑같은 알고리즘이며 값의 범위만 다르기 때문에 long long 을 사용하였습니다.

2. int 의 범위 –2,147,483,648 ~ 2,147,483,647

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 2020/10/28 - [분류 전체보기] - [알고리즘] c++ cpp 가장 긴 증가하는 부분 수열 2

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

using namespace std;

int main() {
	int n;
	long long temp;
	int cnt=0;
	vector<long long> 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);
			*it = temp;
		}
	}

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

	return 0;
}