가장 긴 증가하는 부분 수열 4

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 11053번 - 가장 긴 증가하는 부분 수열 풀이
  • 위의 풀이에 부분 수열의 구성을 찾아낼 수 있는 코드를 추가하면 됩니다.
  • 부분 수열이 결정될 때 어떤 부분 수열이 추가되는 지(즉, 마지막에 어떤 값이 오는 수열인지)를 기록합니다.
  • 그리고 결과를 출력할 때 뒤에서부터 앞으로 한 단계씩 추적해가면서 출력해주면 됩니다.
  • 앞 단계가 없을 경우를 위해서 -1로 초기화 하고 진행합니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const N = parseInt(input[0]);
	const arr = input[1].split(" ").map(Number);
	const dp = Array.from({length: N}, () => 1);
	const before = Array.from({length: N}, () => -1);

	for (let i = 1; i < N; i++) {
		for (let j = i - 1; j >= 0; j--) {
			if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				before[i] = j;
			}
		}
	}

	let max = 0;
	let maxIdx = 0;
	for (let i = 0; i < N; i++) {
		if (max < dp[i]) {
			max = dp[i];
			maxIdx = i;
		}
	}

	const res = [];
	while (maxIdx != -1) {
		res.push(arr[maxIdx]);
		maxIdx = before[maxIdx];
	}

	return `${max}\n${res.reverse().join(" ")}`;
};

console.log(solution(input));