백준 2352번 C++

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 40001;
int n;
int line[MAX];
int cache[MAX];

int maxline() {
	cache[0] = line[1];
	int size = 0;

	for (int i = 2; i <= n; i++) {
		if (cache[size] < line[i])
			cache[++size] = line[i];
		else {
			int index = lower_bound(cache, cache + size, line[i]) - cache;
			cache[index] = line[i];
		}
	}
	return size+1;
}

int main(void) {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> line[i];
	cout << maxline() << endl;
}