[코드업] 3736 - LIS (Large)

LIS(Longest Increasing subsequence)란 최장 증가 부분수열을 말한다.

프로그래밍 문제를 풀 다 보면 이것을 응용하는 문제가 많이 출제되고 있고, 동적계획법의 대표적인 사용 예 중 하나이다.

다음과 같은 원소의 개수가 8개(N)인 수열이 있을 때,

1 3 2 9 7 8 5 10

LIS = 1 2 7 8 10 으로 그 길이는 5이다.

이번에는 데이터의 크기가 크므로 O(n^2)알고리즘으로는 해결할 수 없을 것이다.

입력

첫째줄에 수열의 원소개수 N이 입력된다.( 1 <= N <= 100,000 )

둘째 줄에 N개의 원소가 순서대로 공백으로 구분되어 입력된다. ( 1 ~ 200,000 )

출력

최장 증가 부분수열의 길이를 출력한다.

입력 예시 

8
1 3 2 9 7 8 5 10

출력 예시

5

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N;
vector<int> vec;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;
	vec.push_back(-987654321);

	int ret = 0;
	int num;
	for(int i = 0; i < N; i++){
		cin >> num;
		if(vec.back() < num){
			vec.push_back(num);
			ret++;
		}
		else *lower_bound(vec.begin(), vec.end(), num) = num;
	}

	cout << ret;

	return 0;
}