#백준_12738 가장 긴 증가하는 부분 수열 3 - Java

# 유형 : 이분 탐색, LIS

# 12015 문제와 같은 방식이지만, 주어진 숫자의 범위만 잘 확인하고 풀면 된다. LIS 문제는 세그먼트 트리로도 풀 수 있다. 

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

package bj;

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

public class p12738 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		ArrayList arrList = new ArrayList<>();
		arrList.add(-1000000001);
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++) {
			int next = arr[i];
			if(arrList.get(arrList.size()-1) < next) {
				arrList.add(next);
			}else {
				int left=0;
				int right=arrList.size()-1;
				while(left<right) {
					int middle = (left+right)/2;
					if(arrList.get(middle) < next) {
						left = middle+1;
					}else {
						right = middle;
					}
				}
				arrList.set(right, next);
			}
		}
		System.out.println(arrList.size()-1);
	}
}