[Gold 4] 14002번 가장 긴 증가하는 부분 수열 4

import java.io.*;

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());
        String[] arr = br.readLine().split(" ");
        int[] len = new int[n];
        int[] afterIdx = new int[n];
        int max = 0;
        int maxIdx = 0;
        String ans = "";
        
        for(int i=0; i<n; i++) {
            len[i] = 1;
            for(int j=0; j<i; j++) {
                if(Integer.parseInt(arr[i])>Integer.parseInt(arr[j]) && len[i]<len[j]+1) {
                    len[i] = len[j]+1;
                    afterIdx[i] = j;
                }
            }
        }
        
        for(int i=0; i<n; i++) {
            if(max<len[i]) { max = len[i]; maxIdx = i; }
        }
        
        System.out.println(max);
        
        while(true) {
            ans = arr[maxIdx] + " " + ans;
            if(afterIdx[maxIdx]!=0) {
                maxIdx = afterIdx[maxIdx];
            } else {
                if(Integer.parseInt(arr[maxIdx])>Integer.parseInt(arr[afterIdx[maxIdx]])) {
                    maxIdx = afterIdx[maxIdx];
                    ans = arr[maxIdx] + " " + ans;
                }
                
                break;
            }
        }
        
        System.out.println(ans);
    }
}