BOJ 백준온라인져지 12738 가장 긴 증가하는 부분 수열 3 풀이

1. LIS

2. O(NlgN)

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/12738
	* BOJ 백준온라인져지 12738 가장 긴 증가하는 부분 수열 3 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	String str1[] = br.readLine().split(" ");
	int arr[] = new int[N];
	arr[0] = Integer.parseInt(str1[0]);
	int size = 1;
	for (int i = 1; i < N; i++) {
	int h = Integer.parseInt(str1[i]);
	if (arr[size - 1] < h) arr[size++] = h;
	else {
	int l = 0;
	int r = size;
	int m = 0;
	while (l < r) {
	m = (l + r) / 2;
	if (arr[m] < h) l = m + 1;
	else r = m;
	}
	arr[r] = h;
	}
	}
	bw.write(String.valueOf(size));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

출처

• 문제를 만든 사람: baekjoon