📌 About

최장 증가 부분 수열 알고리즘은 주어진 data list에서 증가하는 부분 수열 중 가장 긴 부분 수열을 구하는 방법이다. 추가적으로 이분 탐색을 사용하여 탐색하며 O(NlogN)의 시간이 소요된다.

📌 Algorithm

Step 0. 부분 수열을 저장할 List와 주어진를 data 배열 array를 초기화한다.

이 때 첫 번째 원소의 비교를 위해 모든 원소보다 작은 값을 삽입한다.

예를 들어 양수 원소들만 주어진다면 List에 0을 삽입한다.

**List<T> list = new ArrayList<>(Collections.singleton(T.MIN_VALUE));**

Step 1. 주어진 data array를 차례대로 탐색한다.

Step 2. 탐색하는 data가 list의 마지막 값보다 크면 List에 삽입한다.

Step 3. 탐색하는 data가 list의 마지막 값보다 크지 않다면 이분 탐색을 한다.

Step 3-1. 이분 탐색은 탐색한 data보다 크면서 list에서 가장 작은 값을 찾는 것이다.

Step 3-2. 찾은 data와 현재 탐색한 data를 교체한다.

Step 4. 최종적인 List가 LIS의 길이이다. (최초에 삽입한 T.MIN_VALUE는 빼줘야 한다.)

📌 Java Code

public class LIS {

    private final int[] array;

    public LIS(int[] array) {
        this.array = array;
    }

    public int run() {
        List<Integer> list = new ArrayList<>(Collections.singleton(0));
        for (int value : array)
            if (list.get(list.size() - 1) < value) list.add(value);
            else binarySearch(list, value);
        return list.size() - 1;
    }

    private void binarySearch(List<Integer> list, int value) {
        int left = 0, right = list.size() - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (list.get(mid) >= value) right = mid;
            else left = mid + 1;
        }
        list.set(right, value);
    }
}

📌 Example

다음과 같은 array가 주어진다고 가정해보자. 사실 List 처음에는 0이 있으나 생략하였다.

이후부터는 Array의 원소들을 차례대로 탐색한다.

List는 LIS를 만들기 위한 자료구조이며 실제 LIS는 LIS 배열에 있다.

만약 동일한 최장 길이 부분 수열이라면 우선 탐색된 LIS를 선택한다.

첫 번째 원소인 10을 탐색한다.