P.12015 가장 긴 증가하는 부분 수열 2

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    static int n;
    static int[] arr;
    static ArrayList<Integer> seq;

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

        n = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        seq = new ArrayList<>();

        seq.add(arr[0]);
        for (int i = 1; i < n; i++) {
            if (arr[i] > seq.get(seq.size() - 1)) seq.add(arr[i]);
            else binarySearch(arr[i]);
        }

        bw.write(Integer.toString(seq.size()));
        bw.flush();
    }

    private static void binarySearch(int target) {
        int start = 0, end = seq.size() - 1;
        while (start < end) {
            int mid = (start + end) / 2;

            if (seq.get(mid) < target) start = mid + 1;
            else end = mid;
        }

        seq.set(end, target);
    }
}

코드 설명

LIS 알고리즘 중 O(NlogN)이 소요되는 알고리즘을 사용했다.

(아래 글에서는 두 번째 알고리즘이다.)

https://namu.wiki/w/최장%20증가%20부분%20수열

최장 증가 부분 수열 - 나무위키