접근

전의 문제에서 그냥 경로를 확인해주면 된다.
나는 현재 인덱스에서 부모인덱스가 무엇인지 나타내주는 배열을 하나 더 선언하여서 값이 바뀔때마다 현재 인덱스의 부모 인덱스의 값도 바꿔주었다.

그리고 최대 값을 찾았을때 그 값부터 따라가면서 값을 나타내주었다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N,ret,maxPos,temp;
int arr[1004];
int dp[1004];
int dir[1004];

vector<int> tot;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N;
    
    for(int i=0;i<N;i++) {
        cin >> arr[i];
    }
    
    ret=dp[0];
    dir[0]=0;
    for(int i=1;i<N;i++) {
        for(int j=0;j<i;j++) {
            if(arr[i]>arr[j]) {
                dp[i]=max(dp[j]+1,dp[i]);
                
                if(dp[i]==dp[j]+1) {
                    dir[i]=j;
                }
                ret=max(dp[i],ret);
                
                if(ret==dp[i]) {
                    maxPos=i;
                }
            }
        }
    }
    
    cout << ret+1 << "\n";
    
    if(maxPos==0) {
        cout << arr[maxPos] << "\n";
    }
    else {
        while(maxPos!=0) {
            temp=arr[maxPos];
            tot.push_back(temp);
            maxPos=dir[maxPos];
        }
        
        if(arr[maxPos]<temp) {
            tot.push_back(arr[maxPos]);
        }

        reverse(tot.begin(), tot.end());
        
        for(int a:tot) {
            cout << a << " ";
        }
        cout << "\n";
    }
    

    return 0;
}