N12738 - 가장 긴 증가하는 부분 수열 3

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {
    final static BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    final static BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) throws IOException {
        ArrayList<Integer> arr = input();

        solution(arr);
        sb.setLength(sb.length() - 1);
        BW.write(sb.toString());
        BW.close();
        BR.close();
    }

    public static ArrayList<Integer> input() throws IOException {
        ArrayList<Integer> arr = new ArrayList<>(Integer.parseInt(BR.readLine()));
        st = new StringTokenizer(BR.readLine());

        while (st.hasMoreTokens())
            arr.add(Integer.parseInt(st.nextToken()));

        return arr;
    }

    public static void solution(ArrayList<Integer> arr) {
        int idx;
        ArrayList<Integer> tmp = new ArrayList<>();
        ArrayList<Integer> idxLst = new ArrayList<>();
        tmp.add(arr.get(0));

        for(int i: arr){
            idx = binarySearch(tmp, i);
            if(tmp.get(idx) < i) {
                idx++;
                if(idx == tmp.size()) tmp.add(i);
                else tmp.set(idx, i);
            } else
                tmp.set(idx, i);
            idxLst.add(idx);
        }


        for(int i = idxLst.size()-1; i>=0; i--) {
            if(tmp.get(Math.min(idxLst.get(i)+1, tmp.size()-1)) > arr.get(i))
                tmp.set(idxLst.get(i), arr.get(i));
        }

        sb.append(tmp.size()).append("\n");
        for(int i: tmp) sb.append(i).append(" ");
    }


    public static int binarySearch(ArrayList<Integer> arr, int target) {
        int min = 0;
        int max = arr.size()-1;
        int mid;

        while(min < max) {
            mid = (min + max) / 2;
            if(arr.get(mid) < target) min = mid+1;
            else if(arr.get(mid) > target) max = mid-1;
            else return mid;
        }
        return min;
    }
}