LIS(Longest Increasing Sequence): 최장 증가 부분수열
DP + lower_bound
이러한 배열이 존재한다고 가정을 했을 때 LIS는 가장 길게 증가하는 부분 수열을 구하는 방법이다.
따라서 가장 길게 증가하는 경우를 찾으면 10, 14, 15, 35, 45를 선택했을 때이다.
이러한 수열을 찾기 위해 LIS를 이용하면 O(NlogN)의 시간 복잡도로 구할 수 있다.
가장 길게 증가하는 부분 수열의 개수를 구하려고 할 때 앞에서부터 순차적으로 탐색하면서 증가하는 가장 긴 길이를 구해준다.
lower_bound를 이용해서 구한 LIS알고리즘
vector<int> vec(N + 1), temp;
for (int i = 0; i < N; i++) {
int idx = lower_bound(temp.begin(), temp.end(), vec[i]) - temp.begin();
if (idx == temp.size())
temp.push_back(vec[i]);
else
temp[idx] = vec[i];
}
한 바퀴를 도는데 N번이 걸리고 이때마다 lower_bound(O(logN))를 이용해서 값의 위치를 찾아주기 때문에 LIS의 시간 복잡도는 O(NlogN)이다.
temp배열은 아래와 같이 저장된다.
LIS를 이용한 대표적인 문제:
https://www.acmicpc.net/problem/11053 (가장 긴 증가하는 부분 수열)
