백준_가장 긴 증가하는 부분수열2_12015

//알고리즘 

1. dp

 

2. 이분탐색을 이용하여 dp테이블을 구현

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

public class 가장긴증가하는부분수열2_12015 {
	static int N, arr[], LIS[];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		LIS = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int size = 0;
		for (int i = 0; i < N; i++) {
			int tmp = Arrays.binarySearch(LIS, 0, size, arr[i]);

			if (tmp >= 0)
				continue;
			tmp = Math.abs(tmp) - 1;
			LIS[tmp] = arr[i];

			if (tmp == size) {
				++size;
			}
		}

		System.out.println(size);

	}

}

 

※ 이전 문제와 다르게 2중 for문으로는 해결할 수 없는 문제. 시간복잡도 nlogn으로 해결 가능함.