최장 증가 부분수열: LIS (Longest Increasing Sub-sequence)

LIS 길이는 꽤 단순하게 구할 수 있다.

10 20 10 30 20 50의 전체 수열이 있다면

먼저 10을 벡터에 넣는다

10 

그 다음 수를 벡터의 마지막 수와 비교하여 

1) 마지막 수보다 크다면 그대로 벡터에 삽입

10 20

2) 마지막 수보다 작거나 같다면 벡터에 있는 요소들 중 다음 수보다 크거나 같은 가장 작은 정수를 찾아 바꿔주면 된다.

10 20 (세번째 10과 첫번째 원래 들어있던 10을 바꾼것이다)

이 수를 찾을 때 lower_bound를 사용하면 편하지만 실력 향상을 위해 직접 이분탐색을 구현하여 써봐도 좋다.

끝까지 반복하면 

10(2) 20(4) 30(3) 50(5) ()안에 수는 인덱스이다

의 결과를 얻을 수 있는데 이것은 부분 수열의 길이가 4라는 것이지 이 결과가 최장 증가 부분수열 자체가 되는게 아니다.

최장 증가 부분수열을 구하기 위해서 인덱스를 저장해야하는데, 이는 다음 포스팅에서 다루도록 하겠다.

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;
typedef long long ll;
int n;
int arr[1000001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	vector<int> v;
	v.push_back(arr[0]);
	for (int i = 1; i < n; i++) {
		if (arr[i] > v.back()) {
			v.push_back(arr[i]);
		}
		else {
			auto it = lower_bound(v.begin(), v.end(), arr[i]);
			*it = arr[i];
		}
	}
	cout << v.size();
}