Boj12738 가장 긴 증가하는 부분 수열3

Published: May 02, 2019 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

dp + 이진탐색을 이용하여 문제 해결. lis 알고리즘에 이진탐색을 더하여 문제를 해결하면 log(n) 만에 문제를 해결할 수 있다.

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

using namespace std;

vector<int> v;
int arr[1000010],n;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	
	for (int i = 0; i < n; i++) {
		if (v.empty()) v.push_back(arr[i]);
		else {
			auto iter1 = lower_bound(v.begin(), v.end(), arr[i]);
			if (iter1 == v.end()) v.push_back(arr[i]);
			else v[iter1 - v.begin()] = arr[i];
		}
	}
	printf("%d", v.size());
}