Node.js) 백준 14002번: 가장 긴 증가하는 부분 수열4

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(v => v.split(' ').map(Number))
const [N] = input[0];
const arr = input[1];
let dp = new Array(N).fill(1);
let prev = new Array(N).fill(-1);
let max = 1;
let last = 0;


for (let i = 0; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
      prev[i] = j;
      if (max < dp[i]) {
        max = dp[i];
        last = i;
      }
    }
  }
}
let answerArr = [];

while (last >= 0) {
  answerArr.unshift(arr[last]);
  last = prev[last]
}
console.log(max);
console.log(answerArr.join(' '));