#백준_12015 가장 긴 증가하는 부분 수열 2 - Java

# 유형 : 이분탐색, 최장 증가 수열 활용

# 가장 긴 증가하는 부분 수열1 같은 경우에는 O(N^2)로 통과할 수 있었지만, 여기서는 1000000 * 1000000 = 시간초과이다.

따라서 이분 탐색을 활용한다면 시간초과를 해결할 수 있다. 다이나믹 프로그래밍으로도 풀 수 있다.

package bj;

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

public class p12015 {
	static int N;
	static int max = 0;
	static int arr[],dp[];
	static ArrayList arrList = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arrList.add(-99999);
		arr = new int[N];

		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 val = arr[i];
			if(arrList.get(arrList.size()-1) < val) {
				arrList.add(val);
			}else {
				int left=0;
				int right = arrList.size()-1;
				while(left<right) {
					int middle = (left+right)/2;
					if(arrList.get(middle) < val) {
						left = middle + 1;
					}else
						right = middle;
				}
				arrList.set(right, val);
			}
		}
		System.out.println(arrList.size()-1);
		
	}
}