[Javascript][BOJ] 11055 가장 큰 증가 부분 수열

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

비슷한 알고리즘으로는 LIS가 있는데, LIS가 기억나지 않아서 급하게 찾아보았던 문제였다 ㅜㅜ

 

핵심아이디어

주어진 수열에서, 증가하는 부분수열 중 가장 합이 큰 것을 구하는 문제이다.

당연히 모든 경우의 수를 탐색할 수 없으므로, dp를 사용해야한다.

dp[i] 를 i번째 까지의 수에서 가장 큰 증가하는 부분수열의 합이라고 정의한다.

그럼 dp의 초기상태는 주어진 숫자들의 배열과 같아지게 된다.

i를 1부터 n까지 순회하며, 매 순간 j를 1부터 i까지 순회한다. (2중 for문)

 

i번째 수와 j번째 수를 비교하여 증가하는 부분 수열인지 판단하고,

dp[j] + i번째 수가 기존 dp[i]보다 크다면 값을 덮어씌워준다.

 

dp에서 가장 큰 값을 구한다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

const solution = function (input) {
	const n = parseInt(input.shift());
	const numbers = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));
	numbers.unshift(0);
	// dp[1] => arr 1번째까지의 증가 부분 수열중에 합이 가장 큰 수
	const dp = Array.from({ length: n + 1 }, () => 0).map((_, i) => numbers[i]);
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j < i; j++) {
			if (numbers[j] < numbers[i]) {
				// 증가수열인가?
				dp[i] = Math.max(dp[i], dp[j] + numbers[i]);
			}
		}
	}

	console.log(Math.max(...dp));
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});