가장 긴 증가하는 부분 수열 4

풀이

이 문제는 최적화 문제의 답을 계산하는 문제입니다. 동적 계획법 테크닉을 보면 쉽게 해결할 수 있습니다.
최대 증가 부분 수열 문제에서 사용했던 알고리즘에 몇가지만 더 추가하면 됩니다. 이전 문제에서 사용했던 $lis()$ 함수에서 매 부분 문제마다 어떤 답을 선택했는지 저장하면 됩니다.

구현

import java.util.*;

public class Main {

    public static int N;
    public static int[] cache, A, choices;
    public static ArrayList<Integer> result;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        A = new int[N];
        cache = new int[N + 1];
        choices = new int[N + 1];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
    }

    public static void solve() {
        lis(-1);
        result = new ArrayList<>();
        reconstruct(-1, result);
    }

    // A[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 메소드
    public static int lis(int start) {
        if (cache[start + 1] != 0) return cache[start + 1];

        cache[start + 1] = 1;
        int bestNext = -1;
        for (int next = start + 1; next < N; next++) {
            if (start == -1 || A[start] < A[next]) {
                int temp = lis(next) + 1;
                if (temp > cache[start + 1]) {
                    cache[start + 1] = temp;
                    bestNext = next;
                }
            }
        }
        choices[start + 1] = bestNext;
        return cache[start +  1];
    }

    // A[start]에서 시작하는 LIS를 list에 저장하는 메소드
    public static void reconstruct(int start, ArrayList<Integer> list) {
        if (start != -1) list.add(A[start]);
        int next = choices[start + 1];
        if (next != -1) reconstruct(next, list);
    }

    public static void output() {
        System.out.println(result.size());
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = 1;
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

하나하나 생각한다면 어렵지 않게 구현할 수 있습니다.

회고