백준 11055번: 가장 큰 증가 부분 수열 - javascript

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

문제 설명

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

접근

이 문제는 14002번 가장 긴 증가하는 부분 수열 4와 똑같다. 그냥 다를게 없다. 다른점이라하면 이번엔 수열의 길이가 아니라 합을 비교하는 정도?…
그리고 합을 비교하기 위해 원본배열과 dp배열 맨앞에 강제로 0을 추가했다는 정도이다.

풀이는 다음과 같다.

-	0	1	2	3	4	5	6	7	8	9	10
원본 배열	-	1	100	2	50	60	3	5	6	7	8
dp 배열	0	-	-	-	-	-	-	-	-	-	-

이렇게 원본과 dp배열 맨앞에 0을 두고 시작한다.

-	0	1	2	3	4	5	6	7	8	9	10
원본 배열	-	1	100	2	50	60	3	5	6	7	8
dp 배열	0	1	-	-	-	-	-	-	-	-	-

1번째값 1보다 작은 수 들 중에서 최대값은 0이므로 dp[1]은 1이다.

-	0	1	2	3	4	5	6	7	8	9	10
원본 배열	-	1	100	2	50	60	3	5	6	7	8
dp 배열	0	1	101	-	-	-	-	-	-	-	-

2번째값 100보다 작은 수 들 중에서 최대값은 1이므로 dp[2]는 100+1이다.

-	0	1	2	3	4	5	6	7	8	9	10
원본 배열	-	1	100	2	50	60	3	5	6	7	8
dp 배열	0	1	101	3	-	-	-	-	-	-	-

3번째값 2보다 작은 수 들 중에서 최대값은 1이므로 dp[3]은 1+2…
이런식으로 진행하게되면 우리는 아래와 같은 결과물을 얻게 된다.

-	0	1	2	3	4	5	6	7	8	9	10
원본 배열	-	1	100	2	50	60	3	5	6	7	8
dp 배열	0	1	101	3	53	113	5	10	16	23	31

이렇게 나온 dp배열의 max값을 반환하면 정답이 나온다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer = '';
  let n = input[0];
  let arr = '0 '+ input[1]
  arr = arr.split(' ')
  answer = max_array_sum(n, arr);  
  console.log(answer)
  process.exit();
});

function max_array_sum(n, arr){
  let dp = new Array(parseInt(n)+1).fill(0)
  for(let i=1;i<=n;i++){
    let max = 0;
    for(let j=0;j<i;j++){      
      if(arr[j]*1<arr[i]*1){
        max = Math.max(dp[j], max);
      }
    }
    dp[i] = arr[i]*1 + max
  }
  return Math.max(...dp)
}