LIS 알고리즘 개념

풀이

풀이는 제 이전 블로그에서 확인 가능합니다.

소스코드 : LIS 3

#include<iostream>
using namespace std;

int n, len;

int arr[1000000];
int lis[1000000];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;

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

	len = 1;
	lis[0] = arr[0];
	
	for (int i = 1; i < n; ++i) {
		int l = 0;
		int h = len;
		int upper_bound = h;

		while (l <= h) {
			int mid = (l + h) / 2;
			if (lis[mid] < arr[i]) {
				l = mid + 1;
			}
			else if (lis[mid] >= arr[i]) {
				upper_bound = mid;
				h = mid - 1;
			}
		}

		lis[upper_bound] = arr[i];
		if (len == upper_bound) {
			len += 1;
		}

	}
	cout << len;
}

주의점

upper bound를 확실히 구할 것!

해당 값을 제대로 구했는지 확인할 요소

1. while(lo < hi) 가 아니라 while(lo <= hi) 인지

7
4 5 6 1 2 3 4

정답 : 4