백준(BOJ) 1965 상자넣기 *

# LIS

LIS 개념을 알고 푸는것이 좋당.

최장 증가 수열(LIS,Largest Increasing Sequence) 알고리즘

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 100005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n, m, ans = 0;
vector<int> v;
int main()
{
	scanf("%d", &n);
	v.push_back(-INF);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &m);
		if (v.back() < m)
		{
			v.push_back(m);
			ans++;
		}
		else
		{
			auto it = lower_bound(v.begin(), v.end(), m);
			*it = m;
		}
	}
	printf("%d", ans);
	return 0;
}