백준 12015 가장 긴 증가하는 부분 수열 2

백준 12015
최장 증가 부분 수열 (LIS,Longest Increasing Subsequence)의 알고리즘은 두개가 있는데, 하나는 dp를 이용하는 방법이고 하나는 이분탐색을 이용하는 방법이다. n이 매우 클 때, 시간 복잡도를 개선하기 위해 후자의 방법을 사용하면 된다.
전자의 경우

for(int i=0;i<n;i++){
	for(int j=0;j<i;j++){
    	if(arr[i]>arr[j]) dp[i]=max(dp[i],dp[j]+1);
    }
}

후자의 경우
1. 처음 vector에 첫 번째 수열의 원소를 넣어준다.
2. vector의 맨 뒤의 원소와 삽입하려는 x를 비교한다.
2.1 x가 맨 뒤의 원소보다 크다면 vector에 push_back을 한다.
2.2 x가 맨 뒤의 원소보다 작거나 같다면 lower bound(x)를 이용해서 나온 원소를 x로 변경한다.
=> lower bound(x)가 x와 같거나 큰 원소를 탐색함으로 그 위치에 x를 넣어도 수열의 증감소는 변함이 없다.

ex) vector = { -2 , 5 , 8} 
x= 7 -> lower_bound(7) = 8 -> 8을 7로 바꾸면 된다.
최종 vector = { -2 ,5 ,7}

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int arr[1000001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) cin >> arr[i];

	v.push_back(arr[0]);

	for (int i = 1; i < n; i++) {	

		if (v[v.size() - 1] < arr[i]) {
			v.push_back(arr[i]);
		}
		else {
			int x = lower_bound(v.begin(), v.end(), arr[i])-v.begin();
			v[x] = arr[i];
		}
	}

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

}