[백준 / 골드4] 14002 가장 긴 증가하는 부분 수열 4 (Java)

문제 보기

사용한 것

• 점화식을 세워 풀이하기 위한 bottom-up

풀이 방법

• i보다 작은 수 j에서 arr[j] < arr[i] 일때 증가하는 부분 수열이 될 수 있으므로 dp[i] = Math.max(dp[j] + 1, dp[i])
• 증가하는 부분 수열을 출력해야 하므로 Stack을 사용해서 역으로 추적

코드

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());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxLen = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    maxLen = Math.max(dp[i], maxLen);
                }
            }
        }
        sb.append(maxLen).append("\n");

        int len = maxLen;
        Stack<Integer> stack = new Stack<>();
        for (int i = n; i > 0; i--) {
            if (dp[i] == len) {
                stack.push(arr[i]);
                len--;
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        System.out.println(sb);

        br.close();
    }
}