LIS 알고리즘 개념

#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;
}

7
4 5 6 1 2 3 4

정답 : 4