[백준] 1912. 연속합 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍)

 

문제를 풀기 위한 아이디어

1. 직전까지의 부분합 + 현재 가리키고 있는 수 

2. 현재 가리키고 있는 수

를 비교하여 더 큰 값을 부분합으로 저장한다.

즉, 지금까지 연속해서 더한 부분합+현재 가리키고 있는 수와 그냥 현재 가리키고 있는 수를 비교했는데 현재 가리키고 있는 수가 더 크다면 미련없이 이전 수들을 버리고 새롭게 시작하여도 OK라는 것이다.

 

예제 1을 가지고 예를 들어보면, [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]에서

dp[7]까지는 쭉 더하다가 8번째 수인 12를 만났을 때 -14 + 12 vs 12를 비교해서 12가 더 크기 때문에 이전 값을 다 버리고 12부터 시작하는 것이다.

그렇게 해서 구한 모든 dp 값 중 최댓값을 출력하면 된다.

 

내가 구현한 코드 (자바스크립트)

let fs = require("fs");
let numbers = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(numbers[0]);
numbers = numbers[1]
  .trim()
  .split(" ")
  .map((element) => Number(element));
numbers.unshift(0);
const dp = new Array(N + 1);
dp[0] = numbers[1];
dp[1] = numbers[1];

for (let i = 2; i <= N; i++) {
  // 직전까지의 부분 합 + 현재 값  : dp[i-1] + numbers[i]
  // 현재 값 : numbers[i]
  if (dp[i - 1] + numbers[i] >= numbers[i]) {
    // 직전까지의 부분 합 + 현재 값이 가장 클 때
    dp[i] = dp[i - 1] + numbers[i];
  } else {
    // 현재 값이 가장 클 때
    dp[i] = numbers[i];
  }
}
console.log(Math.max(...dp));