[C++] 12738 : 가장 긴 증가하는 부분 수열 3

골드 Ⅱ

 

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

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	int s;
	scanf("%d", &s);
	vector <int> subsq;
	subsq.push_back(s);

	int idx;
	for (int i = 1; i < n; i++) {
		scanf("%d", &s);
		if (subsq.back() < s) {
			subsq.push_back(s);
		}
		else {
			idx = lower_bound(subsq.begin(),subsq.end(), s) - subsq.begin();
			subsq[idx] = s;
		}
	}
	printf("%d", subsq.size());
} 

 

LIS 알고리즘 (nlogn, LIS의 길이만 출력)

 

가장 긴 증가하는 부분 수열 2 문제와 완전히 동일한 코드

가장 긴 증가하는 부분 수열 2 와 다른 조건은

 

주어지는 seq들이 음수일 수도 있다는 것

 

가장 긴 증가하는 부분 수열 2에서 구현한 로직에서 문제가 되는 부분이 아니므로 그대로 제출함