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

[문제]

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

 

[풀이]

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

해당 문제는 [Java] BOJ/백준 12015번 가장 긴 증가하는 부분 수열 2과 수열 A의 원소 Ai의 범위가 음수까지 포함인 부분만 다르고 완전히 일치한다. 따라서 같은 코드를 제출해도 통과할 수 있다.

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] seq = new int[n];
        for (int i = 0; i < n; i++) seq[i] = Integer.parseInt(st.nextToken());

        ArrayList<Integer> LIS = new ArrayList<>();
        LIS.add(seq[0]);
        for (int i = 1; i < n; i++) {
            int key = seq[i];

            if (LIS.get(LIS.size() - 1) < key) LIS.add(key);
            else {
                int low = 0;
                int high = LIS.size() - 1;
                while (low < high) {
                    int mid = (low + high) / 2;
                    if (LIS.get(mid) >= key) high = mid;
                    else low = mid + 1;
                }
                LIS.set(high, key);
            }
        }
        System.out.println(LIS.size());
    }
}