12015 번 가장 긴 증가하는 부분 수열2

12015번: 가장 긴 증가하는 부분 수열 2

 

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(br.readLine());
    StringTokenizer st=new StringTokenizer(br.readLine());
    int []arr=new int[n+1];
    for(int i=1;i<=n;i++){
        arr[i]=Integer.parseInt(st.nextToken());
    }
    ArrayList<Integer>list=new ArrayList<>();
    list.add(arr[1]);
    for(int i=2;i<=n;i++){
        int num=arr[i];
    
        if(num>list.get(list.size()-1)){
            list.add(num);
        }
        else{
            int left=0;
            int right=list.size()-1;
            while(left<right){
                int mid=(left+right)/2;
                if(num<=list.get(mid)){
                    right=mid;
                }
                else{
                    left=mid+1;
                }
            }
            list.set(left,num);
        }
        
    }
        System.out.println(list.size());
    }
}

 

 

 

가장 작은 끝 값은 이분 탐색을 통햇 찾아서 값을 바꾸어 주자.