문제

풀이

• 리스트 초기값 [0]
• 숫자가 리스트 가장 맨 끝 숫자보다 크면 리스트 끝에 추가
• 작으면 리스트에서 이분탐색으로 크거나 같은 숫자 인덱스 찾아서 replace

  LIS 최대 길이를 찾는데에만 적용

---

코드

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));
        StringTokenizer st;
//        System.out.println(new Solution().solution(3,4,2,3,3,1,5));
        int n=Integer.parseInt(br.readLine());
        st=new StringTokenizer(br.readLine());

        ArrayList<Integer> arr=new ArrayList<>();
        arr.add(0);
        for(int i=0;i<n;i++){
            int num=Integer.parseInt(st.nextToken());
            if(num<=arr.get(arr.size()-1)){
                func(arr,num);
            }
            else arr.add(num);
        }
        System.out.println(arr.size()-1);
    }

    static void func(ArrayList<Integer> arr,int num){
        int l=1;
        int r=arr.size()-1;
        int mid = 0;
        while(l<r){
            mid=(l+r)>>1;
            if(arr.get(mid)>=num){
                r=mid;
            }
            else l=mid+1;
        }
        arr.set(r,num);
    }
}

#이분탐색#LIS