14002 가장 긴 증가하는 부분 수열 4 (JAVA)

• LIS의 길이 를 구한 후, dy 배열을 뒤에서부터 순회하여 실제 수열을 찾는다.

import java.util.Scanner;
import java.util.Stack;

/* 14002 가장 긴 증가하는 부분 수열 4 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int answer = 0;
        int[] arr = new int[n];
        int[] dy = new int[n];
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();

        dy[0] = 1;
        for(int i=1; i<arr.length; ++i){
            int max = 0;
            for(int j=i-1; j>=0; j--){
                if(arr[i] > arr[j] && dy[j] > max)
                    max = dy[j];
            }
            dy[i] = max + 1;
            answer = Math.max(dy[i], answer);
        }
        
	/* -------------- 여기서부터 수열 구하기 -------------- */

        Stack<Integer> stack = new Stack<>();

        int tmp = answer;
        for(int i = arr.length-1; i>=0; --i){
            if(tmp == 0)
                break;
            if(dy[i] == tmp){
                stack.push(arr[i]);
                tmp--;
            }
        }

        if(n==1) {
            System.out.println(1);
            System.out.println(arr[0]);
        }
        else {
            System.out.println(answer);
            while(!stack.isEmpty())
                System.out.print(stack.pop()+" ");
        }
    }
}