[백준] 14003번 가장 긴 증가하는 부분 수열 5 (platinum 5

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

public class Main{
    static int[] num;
    static ArrayList<Integer>[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.valueOf(br.readLine());

        num=new int[n+1];
        Arrays.fill(num,Integer.MAX_VALUE);

        //들어올 수들의 자리마다, 들어온 값들이 인덱스를 저장할 리스트
        //나중에 뒤에서부터, 순서대로 내려오면서, 앞 자리는 뒷 자리보다 큰 인덱스가 오면 안되므로
        //그걸 판단할 기준을 만듦
        arr=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            arr[i]=new ArrayList<>();
        }

        int[] room=new int[n+1];

        StringTokenizer st=new StringTokenizer(br.readLine());
        int start=1;
        int end=1;
        num[1]=Integer.valueOf(st.nextToken());
        arr[1].add(1);
        room[1]=num[1];

        //수들을 들어오면서, index를 자리수 리스트에 넣을 것이므로,
        //각각의 index에 해당하는 자리에 수들을 넣기
        //만약 lis끝부분보다 크면, 그 자리에 넣으므로, end를 통해서
        //+1하여 넣고, 아니면 lis돌리기.
        for(int i=2; i<=n; i++){
            int t=Integer.valueOf(st.nextToken());
            room[i]=t;
            if(t>num[end]){
                end+=1;
                num[end]=t;
                arr[end].add(i);
            }
            else{
                lis(start,end,t,i);
            }
        }

        //뒤에서 부터 내려오면서 index비교를 하면서, 들어올 수들 판단.
        int temp=n+1;
        ArrayList<Integer> answer=new ArrayList<>();
        for(int i=end; i>=1; i--){
            //위와 아래코드의 차이가 존재하는 부분.
            //실제로, index가 큰 값들은 list의 뒷 부분에 들어오게 되므로, 
            //굳이 정렬을 해서 뒤부터 볼 필요 x, 이미 정렬된 상태랑 동일
            //약 200ms차이 발생
            Collections.sort(arr[i]);
            int s=arr[i].size()-1;
            for(int j=s; j>=0; j--){
                int t=arr[i].get(j);
                if(t<temp){
                    answer.add(t);
                    temp=t;
                    break;
                }
            }
        }

        bw.write(answer.size()+"\n");
        for(int i=answer.size()-1; i>=0; i--){
            bw.write(room[answer.get(i)]+" ");
        }
        bw.flush();

    }

    //lis구현, lis를 통해서, 수들의 순서 정함.
    public static void lis(int s, int e, int temp,int index){
        int mid=0;
        while(s<=e){
            mid=(s+e)/2;
            if(temp>num[mid]){
                s=mid+1;
            }
            else if(temp<num[mid]){
                e=mid-1;
            }
            else{
                break;
            }
        }
        if(num[s]>temp){
            num[s]=temp;
            arr[s].add(index);
        }
    }
}