11055 가장 큰 증가하는 부분 수열

문제 분석

알고리즘: DP

11053번 문제에서는 DP에 오름차순으로 증가하는 부분수열의 ‘길이’를 저장했다면, 해당 문제는 오름차순으로 증가하는 부분수열의 ‘합계’를 저장하고, 각 부분수열의 합계들 가운데 최대값을 출력하는 문제다.

주어진 수열 8 을 A 라고 하고, A를 순회하면서 부분수열의 합계를 저장할 메모제이션 배열을 DP라고 가정해보자.

먼저, DP 배열의 초기화 과정을 거쳐야한다.

이전의 11053번 문제에서는 부분수열의 ‘길이’를 구할때 기본적으로 자기 자신을 포함하기 때문에 DP의 모든 원소를 1로 초기화 했다. 하지만 해당 문제는 ‘합계’를 구하는 문제이므로 1이 아닌 자기 자신의 값을 갖도록 초기화 한다.

DP = [ 1, 100, 2, 50, 60, 3, 5, 6, 7, 8 ]

그리고 각 수열을 대상으로 하는 부분수열의 합을 DP에 저장한다.

A[0] 을 대상으로 하는 부분 수열은 1 이므로 DP[0]=1
A[1] 을 대상으로 하는 부분 수열은 100 이므로 DP[1]=101
A[2] 을 대상으로 하는 부분 수열은 2 이므로 DP[2]=3
A[3]을 대상으로 하는 부분 수열은 50 이므로 DP[3]=53
A[4]를 대상으로 하는 부분 수열은 60 이므로 DP[4]=113
…

위 과정에서 DP에 오름차순 정렬이 가능한 수열들의 누적 합계를 저장하므로 재계산하지 않고 재활용하여 비교가 가능해진다.

이를 보기쉽게 표로 정리해보자면 다음과 같을 것이고, 합계가 저장된 DP 배열에서 최대 값을 출력하면 된다.

A	1	100	2	50	60	3	5	6	7	8
dp	1	101	3	53	113	6	11	17	24	32

여기서 최대 값은 113인 것을 알 수 있다.

풀이

const [N, input] = require('fs').readFileSync('dev/stdin').toString().split('\n');
const n = parseInt(N);
const a = input.split(' ').map(Number);
const dp = [...a]; // dp 초기화

for (let i = 0; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (a[j] < a[i] && dp[i] < dp[j] + a[i]) {
      dp[i] = dp[j] + a[i];
    }
  }
}

console.log(Math.max(...dp)); // 최대값 출력