[Java] 백준 14003 가장 긴 증가하는 부분 수열 5 - 동적 계획법(13)

백준 14003 가장 긴 증가하는 부분 수열 5
문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

---

제출

import java.io.*;
import java.util.*;
public class Main {
	static int N, maxLength;
	static int B[] = new int[1000001];
	static int A[] = new int[1000001];
	static int D[] = new int[1000001];
	static int ans[] = new int[1000001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		int index;
		B[++maxLength] = A[1];
		D[1] = 1;
		for (int i = 2; i <= N; i++) {
			if (B[maxLength] < A[i]) {
				B[++maxLength] = A[i];
				D[i] = maxLength;
			} else {
				index = binarysearch(1, maxLength, A[i]);
				B[index] = A[i];
				D[i] = index;
			}
		}
		System.out.println(maxLength);
		index = maxLength;
		int x = B[maxLength] + 1;
		for (int i = N; i >= 1; i--) {
			if (D[i] == index && A[i] < x) {
				ans[index] = A[i];
				x = A[i];
				index--;
			}
		}
		for (int i = 1; i <= maxLength; i++)
			System.out.print(ans[i] + " ");
	}
	static int binarysearch(int l, int r, int now) {
		int mid;
		while (l < r) {
			mid = (l + r) / 2;
			if (B[mid] < now)
				l = mid + 1;
			else
				r = mid;
		}
		return l;
	}
}

예제

6
10 20 10 30 20 50

결과

백준 14003 가장 긴 증가하는 부분 수열 5

 

14003번: 가장 긴 증가하는 부분 수열 5