가장 큰 증가 부분 수열

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = n 번째 수가 마지막으로 오는 수열 중 합이 가장 큰 증가 부분 수열의 합
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 백준 11053번 가장 긴 증가하는 부분 수열 문제와 비슷하게 풀 수 있습니다.
  • 정의한 dp[n]은 앞에 어떤 수들로 구성된 수열인지는 모르지만 합이 최대인 증가 부분 수열입니다.
  • n 번째의 경우를 생각해보겠습니다.
    • n - 1 번째 수에 이어서 증가 부분 수열이 되는 경우
      • dp[n] = dp[n - 1] + numArr[i]
    • n - 2 번째 수에 이어서 증가 부분 수열이 되는 경우
      • dp[n] = dp[n - 2] + numArr[i]
    • …
    • 1 번째 수에 이어서 증가 부분 수열이 되는 경우
      • dp[n] = dp[1] + numArr[i]
    • 단, 모든 경우 마지막에 오는 수가 n 번째 수보다 작아야 위의 경우가 가능합니다. 그렇게 해야 증가 부분 수열이 될 수 있기 때문입니다. (즉 numArr[n - 1] 이 numArr[n] 보다 작아야 n - 1 번째 경우가 가능)
    • 저 경우들 중에서 가장 큰 값이 dp[n]의 값이 됩니다.
  • 그리고 최종적으로는 dp 배열의 모든 값 중 최대값이 정답이 됩니다.

소스 코드

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

const solution = (input) => {
	const n = parseInt(input[0]);
	const numArr = input[1].split(" ").map(Number);

	// base
	const dp = [numArr[0]];

	for (let i = 1; i < numArr.length; i++) {
		dp[i] = numArr[i];
		for (let j = 0; j < i; j++) {
			if (numArr[j] < numArr[i] && dp[j] + numArr[i] > dp[i])
				dp[i] = dp[j] + numArr[i];
		}
	}

	return Math.max(...dp);
};

console.log(solution(input));