백준(BOJ) 2352 반도체설계 **

# LIS 

최장 증가 수열을 알고 있다면 어렵지 않게 풀 수 있는 문제이다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#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;
}