[백준] 2352번 반도체 설계 (gold 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.valueOf(br.readLine());
        int[] num=new int[n+1];
        StringTokenizer st=new StringTokenizer(br.readLine());

        for(int i=1; i<=n; i++){
            num[i]=Integer.valueOf(st.nextToken());
        }

        int[] dp=new int[n+1];
        int start=1;
        int end=1;
		//lis이용하면 쉽게 풀리는 문제
        dp[1]=num[1];
        for(int i=2; i<=n; i++){
            if(num[i]>dp[end]){
                dp[++end]=num[i];
            }
            else{
                lis(start, end, dp, num[i]);
            }
        }

        int answer=0;
        for(int i=1; i<=n; i++){
            if(dp[i]!=0){
                answer++;
            }
        }
        System.out.println(answer);

    }

    public static void lis(int s ,int e, int[] dp, int input){
        int mid=0;
        while(s<=e){
            mid=(s+e)/2;
            if(input>dp[mid]){
                s=mid+1;
            }
            else if(input<dp[mid]){
                e=mid-1;
            }
        }

        if(dp[s]>input){
            dp[s]=input;
        }

    }
}