문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력

6
10 20 10 30 20 50

예제 출력

4
10 20 30 50

풀이

이전에 풀었던 가장 긴 증가하는 부분 수열 문제에서 부분 수열을 같이 출력하면 되는 문제이다.

부분 수열의 최댓값을 저장했던 dp 배열을 2차원 배열로 바꿔 해당 부분 수열도 같이 저장할 수 있게 바꾼 뒤 최댓값을 찾을 때마다 부분 수열을 concat() 메소드를 사용하여 저장하였다.

작성한 코드는 다음과 같다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const test_num = Number(input.shift());
const test_case = input.shift().split(" ").map(Number);

const dp = new Array(test_num);
dp[0] = [1, [test_case[0]]];

for (let i = 1; i < test_num; i++) {
  let max = [0, []];
  for (let j = 0; j <= i; j++) {
    if (test_case[j] < test_case[i]) {
      if (max[0] < dp[j][0]) {
        max = [dp[j][0], dp[j][1]];
      }
    }
  }
  dp[i] = [max[0] + 1, max[1].concat(test_case[i])];
}

let max_item = [0, []];

dp.forEach((item) => {
  if (item[0] > max_item[0]) max_item = item;
});

console.log(max_item[0]);
console.log(max_item[1].join(" "));