백준 1912번 연속합 node js

문제

링크

 

풀이

dp 유형에 어려움을 겪고 있었는데 처음으로 한번에 맞춘 문제이다.

n개의 정수로 이루어진 임의의 수열이 주어지고

한 개 이상 연속된 수를 선택해서 구할 수 있는 최대합을 구해야한다.

 

다음 임의의 수열이 주어졌다고 하자. sequence = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

해당 수열에서 가장 큰 합은 12 + 21 2개를 선택한 합 33이 최대합이다.

 

떠올린 풀이과정은 핵심 아이디어는 sequence 배열의 각 인덱스마다 최대합을 구하고 마지막에 가장 큰 인덱스 값을 뽑아 내는 것이다.

각 인덱스마다 최대합을 구하여 저장 해놓고 다음 인덱스에서 최대합을 구할 때 활용해야한다. -> dp 활용
dp라는 배열을 만들어 sequence 각 인덱스의 최대합을 구하도록 하겠다.

 

단 두 가지 조건을 염두해어야 한다.

만약 합이 양수이면 합을 저장하고 다음 인덱스의 수를 계속해서 더한다.

만약 합이 음수이면 다음 인덱스 값으로 합을 초기화 한다.

 

dp[0] = 10 -> sequence[0]의 최대합은 이전 값이 없으니 자신의 값이 된다.

dp[1] = 10 + (-4) = 6

dp[2] = 6 + 3 = 9

dp[3] = 9 + 1 = 10

dp[4] = 10 + 5 = 15

dp[5] = 15 + 6 = 21

dp[6] = 21 + (-35) = -14

dp[7] = 12

dp[8] = 12 + 21 = 33

dp[9] = 33 + (-1) = 32

 

위 계산을 하고 나면 각 인덱스의 최대합을 저장한 dp 값은 아래가 된다.

dp = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

 

위 값 중에서 최대 값을 뽑아내면 정답이 된다.

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

const N = Number(input.shift());
const nums = input[0].split(' ').map(Number);

const dp = new Array(N).fill(0);
dp[0] = nums[0];

for(let i=1; i<N; i++) {
      if(dp[i-1] < 0) {
          dp[i] = nums[i];
          continue;
      }
     dp[i] = dp[i-1] + nums[i];
}

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