[Java] 백준 12738번 가장 긴 증가하는 부분 수열 3

다이나믹 프로그래밍, 이분 탐색 문제입니다.

https://j3sung.tistory.com/945

[Java] 백준 12015번 가장 긴 증가하는 부분 수열 2

위 문제와 동일한 코드로 코드를 제출해서 통과했습니다.

동일하게 LIS를 저장하는 리스트를 만들고 값을 넣어줍니다.
리스트의 끝값보다 작은 값이 들어올 경우 이분탐색을 사용해서 리스트 안의 값을 수정해줍니다.
리스트의 끝값보다 큰 값이 들어오는 경우 리스트의 뒤에 붙여줍니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] arr;
	static ArrayList<Integer> dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;

		int ans = 0;
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		dp = new ArrayList<>();

		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) {
			if (dp.size() == 0 || dp.get(dp.size() - 1) < arr[i]) {
				dp.add(arr[i]);
			} else {
				int left = 0;
				int right = dp.size() - 1;
				while (left < right) {
					int mid = (left + right) >> 1;
					if(dp.get(mid) >= arr[i]) {
						right = mid;
					} else {
						left = mid + 1;
					}
				}
				dp.set(right, arr[i]);
			}
		}

		bw.write(dp.size() + "\n");
		bw.close();
	}
}